向上调整(AdjustUp)
代码如下：
void AdjustUp(int* a, int child) { assert(a); int parent = (child - 1) / 2; while (child > 0) { if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } }
这里的向上调整函数就是指定一个元素与其父亲比较，如果孩子小于父亲，就交换
常用于小堆的插入与堆排序。
向下调整(AdjustDown)
代码如下：
void AdjustDown(int* a, int n, int parent) { int child = parent * 2 + 1; while (child < n) { // 选出左右孩子中小的那一个 if (child + 1 < n && a[child + 1] < a[child]) { ++child; } // 如果小的孩子小于父亲，则交换，并继续向下调整 if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } }
这里的向下调整函数就是指定一个元素与其父亲比较，如果孩子小于父亲，就交换
同样常用于小堆的插入与堆排序，和向上调整的不同的就是方向。
堆的初始化(HeapInit)
代码如下：
void HeapInit(HP* hp) { assert(hp); hp->a = NULL; hp->size = hp->capacity = 0; }
堆的销毁(HeapDestroy)
代码如下：
void HeapDestroy(HP* hp) { assert(hp); free(hp->a); hp->capacity = hp->size = 0; }
堆的插入(HeapPush)
代码如下：
void HeapPush(HP* hp, HPDataType x) { assert(hp); if (hp->size == hp->capacity) { size_t newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2; HPDataType* tmp = realloc(hp->a, sizeof(HPDataType)*newCapacity); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } hp->a = tmp; hp->capacity = newCapacity; } hp->a[hp->size] = x; hp->size++; AdjustUp(hp->a, hp->size - 1); }
堆的插入，首先创建内存空间，然后插入元素，size++就不说了；
重点讲一下这里的向上调整，因为是小数往上调，所以这里的调用是用于小堆的建立；
如果要改成大堆，那么就要将向上调整函数的判断改为大于；
修改后代码如下：
if (a[child] > a[parent])
堆的删除(HeapPop)
代码如下：
void HeapPop(HP* hp) { assert(hp); assert(!HeapEmpty(hp)); Swap(&hp->a[0], &hp->a[hp->size - 1]); hp->size--; AdjustDown(hp->a, hp->size, 0); }
堆的删除是删除堆顶的元素，但是需要注意的是并不是直接将堆顶元素直接删除
而是将堆顶元素和最后一个元素交换，再进行size–
再将换上去的最后的元素重新向下调整到相应位置
这样做的目的是为了保持堆的基本结构，否则可能堆结构可能不成立。
取堆顶的数据(HeapTop)
代码如下：
HPDataType HeapTop(HP* hp) { assert(hp); assert(!HeapEmpty(hp)); return hp->a[0]; }
直接返回第一个元素即可
堆的打印(HeapPrint)
代码如下：
void HeapPrint(HP* hp) { for (int i = 0; i < hp->size; ++i) { printf("%d ", hp->a[i]); } printf("\n"); }
常用的for循环对顺序表进行元素遍历逐个打印
堆的判空(HeapEmpty)
代码如下：
bool HeapEmpty(HP* hp) { assert(hp); return hp->size == 0; }
这里使用的是bool值，当然你也可以使用int类型
堆的数据个数(HeapSize)
代码如下：
int HeapSize(HP* hp) { assert(hp); return hp->size; }
堆排序的简易例子
代码如下：
void HeapSort(int* a, int n) { for (int i = (n - 1 - 1) / 2; i >= 0; --i) { AdjustDown(a, n, i); } for (int end = n - 1; end > 0; --end) { Swap(&a[end], &a[0]); AdjustDown(a, end, 0); } } int main() { int a[] = { 70, 56, 30, 25, 15, 10, 75, 33, 50, 69 }; HeapSort(a, sizeof(a) / sizeof(a[0])); for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i) { printf("%d ", a[i]); } printf("\n"); return 0; }
这里我们主要使用向下调整的方法来实现，因为上面对堆的删除是用于小堆
所以这里调用向下调整后，该数组为降序，排序后打印如下：
75 70 69 56 50 33 30 25 15 10
如果要进行升序排序，我们只需将向下调整函数的部分符号修改即可
修改如下：
void AdjustDown(int* a, int n, int parent) { int child = parent * 2 + 1; while (child < n) { if (child + 1 < n && a[child + 1] > a[child]) { ++child; } if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } }
排序后打印如下：
10 15 25 30 33 50 56 69 70 75
结语
有兴趣的小伙伴可以关注作者，如果觉得内容不错，请给个一键三连吧，蟹蟹你哟！！！
制作不易，如有不正之处敬请指出
感谢大家的来访，UU们的观看是我坚持下去的动力
在时间的催化剂下，让我们彼此都成为更优秀的人吧！！！
