一、AdjustUp的基本函数思路
//向上调整，从child开始向上调整 void AdjustUp(HPDataType* a,int child) { int parent = (child - 1) / 2; while (child>0) { if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); //Swap(a[child], a[parent]); //传过去的只是a[child]和a[parent]的值，该函数也只是拿形参接收，对原数组并没有产生实质性的影响 //传过去的是地址 child = parent; parent = (parent - 1) / 2; } else { break; } } }
二、AdjustDown的基本函数思路
void AdjustDown(HPDataType* a,int n,int parent) { assert(a); 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; } } }
建大堆、小堆用AdjustUP和AdjustDown其实都可以，且不管是从前往后遍历还是从后往前遍历
对比AdjustUP和AdjustDown：Adjustdown的时间复杂度更低 O（N），效率更高
对比分析：
后续有时间的时候会补充讲解，敬请关注
三、堆排序的基本实现思路
//传入堆结构基础——数组，数组大小是判断遍历结束的条件 void HeapSort(HPDataType* a,int n) { //升序——建大堆 //降序——建小堆 // 建堆--向上调整建堆 for (int i = 1; i < n; i++) { AdjustUp(a,i); } //建大堆、小堆用AdjustUP和AdjustDown其实都可以，且不管是从前往后遍历还是从后往前遍历 // 那么就得 建大、小堆时候改变一下a[parent]和a[child]之间的关系 //对比AdjustUP和AdjustDown之间，Adjustdown的时间复杂度更低，效率更高 //建堆--向下调整建堆 --O(N) for (int i = (n - 1) - 1 / 2; i > 0; i--) { AdjustDown(a,n,i); } //排序 //升序——建大堆（这里以升序为例） //降序——建小堆 int end = n - 1; while (end>0) { //max换到最后 Swap(&a[0],&a[end]); --end; //让它不动，处理剩下的 //再找到 次max的数 ——重找大堆（不会像直接删除堆顶那样，需要重建堆） AdjustDown(a,end,0); } }
