代碼如下:

#include <stdio.h> #include <assert.h> #include <stdlib.h> #include <string.h>typedef int HDataType;//堆的定義 typedef struct heap {HDataType *data;int size;int capacity; }heap;//交換 void Swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp; }//檢查容量 void checkCapacity(heap * hp) {if (hp->capacity == hp->size){int newC = hp->capacity == 0 ? 1 : 2 * hp->capacity;hp->data = (HDataType *)realloc(hp->data, sizeof(HDataType) * newC);hp->capacity = newC;} }//向下調整 void shiftDown(int *arr, int n, int cur) {int child = 2 * cur + 1;while (child < n){if (child + 1 < n && arr[child + 1] < arr[child]){++child;}if (arr[child] < arr[cur]){Swap(&arr[child], &arr[cur]);cur = child;child = 2 * cur + 1;}else break;} }//向上調整 void shiftUp(int *arr, int n, int cur) {int parent = (cur - 1) / 2;while (cur > 0){if (arr[cur] < arr[parent]){Swap(&arr[cur], &arr[parent]);cur = parent;parent = (cur - 1) / 2;}else break;} }//堆的初始化 void heapInit(heap *hp) {assert(hp);hp->data = NULL;hp->capacity = hp->size = 0; }//堆的創建 void heapCreate(heap * hp, int *arr, int n) {assert(hp);hp->data = (HDataType *)malloc(sizeof(HDataType) *n);memcpy(hp->data, arr, sizeof(HDataType) * n);hp->capacity = hp->size = 0;for (int i = (n - 2) / 2; i >= 0; i--){shiftDown(hp->data, hp->size, i);} }//堆的刪除 void heapPop(heap *hp) {if (hp->size > 0){Swap(&hp->data[0], &hp->data[hp->size - 1]);hp->size--;shiftDown(hp->data, hp->size, 0);} }//獲取堆頂元素 HDataType heapTop(heap *hp) {assert(hp);return hp->data[0]; }//判空 int heapEmpty(heap *hp) {if (hp == NULL || hp->size == 0){return 1;}else return 0; }//堆排序 void heapSort(heap *hp) {assert(hp);for (int i = (hp->size - 2) / 2; i >= 0; i--){shiftDown(hp->data, hp->size, i);}int end = hp->size - 1;while (end > 0){Swap(&hp->data[0], &hp->data[end]);shiftDown(hp->data, end, 0);end--;} }//打印堆 void HeapPrint(heap *hp) {assert(hp);for (int i = 0; i < hp->size; i++){printf("%d ",hp->data[i]);}printf("\n"); }//銷毀堆 void heapDestory(heap *hp) {assert(hp);free(hp->data);hp->data = NULL;hp->capacity = hp->size = 0; }//堆的插入 void heapPush(heap *hp, HDataType val) {assert(hp);checkCapacity(hp);hp->data[hp->size++] = val;shiftUp(hp->data, hp->size, hp->size - 1); }

總結

以上是生活随笔為你收集整理的C语言 实现堆的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。