前面用C语言实现了堆的接口，但是我们会发现用户如果想创建一个大堆和一个小堆，就需要堆代码进行重新修改，这样太过于麻烦。今天我们就用C语言用一个代码来实现两种堆的接口
typedef int HPDataType; typedef int(*PCOM)(HPDataType, HPDataType); // 堆中元素进行小于比较 int Less(HPDataType left, HPDataType right); // 堆中元素进行大于比较 int Greater(HPDataType left, HPDataType right); typedef struct Heap { HPDataType* _array; int _capacity; int _size; PCOM Compare; // 函数指针变量，保存用户传递的比较中堆中元素方法 }Heap; void Swap(HPDataType* x, HPDataType* y) { HPDataType temp = *x; *x = *y; *y = temp; } void CheckCapacity(Heap* hp) { assert(hp); if (hp->_size == hp->_capacity) { int newCapacity = hp->_capacity * 2; HPDataType* pTemp = (HPDataType*)malloc(sizeof(HPDataType)*newCapacity); if (NULL == pTemp) { assert(0); return; } for (int i = 0; i < hp->_size; i++) { pTemp[i] = hp->_array[i]; } free(hp->_array); hp->_capacity = newCapacity; hp->_array = pTemp; } } //堆向下调整算法 void AdjustDown(HPDataType* array, int size, int parent,PCOM Compare) { //默认用child标记parent的左孩子，完全二叉树只有一个孩子的话，一定是左孩子 int child = parent * 2 + 1; //找双亲孩子中较小的孩子 while (child < size){ if (child + 1 < size && Compare(array[child + 1] , array[child])) { child += 1; } if (Compare(array[child] , array[parent])) { Swap(&array[child], &array[parent]); parent = child; child = parent * 2 + 1; } else { return; } } } //堆向上调整算法 void ADjustUP(HPDataType* array, int size, int child,PCOM Compare) { int parent = (child - 1) / 2; while (child) { if (Compare(array[child] , array[parent])) { Swap(&array[child], &array[parent]); child = parent; parent = (child - 1) / 2; } else { return; } } } //空堆的初始化 void InitEmptyHeap(Heap* hp, int capacity, PCOM Compare) { assert(hp); hp->_array = (HPDataType*)malloc(sizeof(HPDataType)*capacity); if (NULL == hp->_array) { assert(0); return; } hp->_capacity = capacity; hp->_size = 0; hp->Compare = Compare; } // 堆中元素进行小于比较 int Less(HPDataType left, HPDataType right) { return left < right; } // 堆中元素进行大于比较 int Greater(HPDataType left, HPDataType right) { return left > right; } //堆的初始化 void InitHeap(Heap* hp, HPDataType* array, int size, PCOM Compare) { assert(hp); hp->_array = (HPDataType*)malloc(sizeof(HPDataType)*size); if (NULL == hp->_array) { assert(0); return; } hp->_capacity = size; for (int i = 0; i < size; i++) { hp->_array[i] = array[i]; } hp->_size = size; hp->Compare = Compare; //找到最后一个非叶子节点 int root = (size - 2) / 2; for (; root >= 0; root--){ AdjustDown(hp->_array, size, root,hp->Compare); } } //在堆中插入元素 void InsertHeap(Heap* hp, HPDataType* data) { CheckCapacity(&hp); hp->_array[hp->_size] = data; hp->_size++; ADjustUP(hp->_array, hp->_size, hp->_size - 1,hp->Compare); } //删除一个堆元素 void EarseHeap(Heap* hp) { if (HeapEmpty(hp)) return; Swap(&hp->_array[0], &hp->_array[hp->_size - 1]); hp->_size -= 1; AdjustDown(hp->_array, hp->_size, 0,hp->Compare); } //获取堆中有效元素个数 int HeapSize(Heap* hp) { assert(hp); return hp->_size; } //判断堆是否为空 int HeapEmpty(Heap* hp) { assert(hp); return 0 == hp->_size; } //获取堆顶元素 HPDataType HeapTop(Heap* hp) { assert(hp); return hp->_array[0]; } //销毁堆 void DestroyHeap(Heap* hp) { assert(hp); if (hp->_array) { free(hp->_array); hp->_capacity = 0; hp->_size = 0; } }