【数据结构与算法】堆排序底层原理

‍ 关于作者会编程的土豆“不是因为看见希望才坚持而是坚持了才看见希望。”你好我是会编程的土豆一名热爱后端技术的Java学习者。正在更新中的专栏《数据结构与算法》《leetcode hot 100》《数据库mysql》作者简介后端学习者先看代码#include iostream #include vector using namespace std; // 下沉调整维护大顶堆性质 void heapify(vectorint arr, int i, int heapSize) { int largest i; // 假设当前节点最大 int left 2 * i 1; // 左子节点 int right 2 * i 2; // 右子节点 // 找出父、左、右三者中的最大值 if (left heapSize arr[left] arr[largest]) largest left; if (right heapSize arr[right] arr[largest]) largest right; // 如果最大值不是父节点交换并递归调整 if (largest ! i) { swap(arr[i], arr[largest]); heapify(arr, largest, heapSize); } } void heapSort(vectorint arr) { int n arr.size(); // 1. 建堆从最后一个非叶子节点开始下沉 for (int i n / 2 - 1; i 0; --i) heapify(arr, i, n); // 2. 排序逐个将堆顶最大值移到末尾 for (int i n - 1; i 0; --i) { swap(arr[0], arr[i]); // 交换堆顶和末尾 heapify(arr, 0, i); // 调整剩余堆 } } // 测试 int main() { vectorint arr {4, 6, 8, 5, 9}; heapSort(arr); for (int x : arr) cout x ; // 输出4 5 6 8 9 return 0; }很多人第一次学堆排序的时候都会卡在一个地方heapify 这玩意到底在干什么代码不长但就是理解不了。这篇文章我们不背模板从“过程”出发把堆排序彻底讲清楚。一、先搞清楚什么是堆堆是一种完全二叉树分两种1. 大顶堆父节点 子节点例如9 / \ 6 8 / \ 5 4特点堆顶根是最大值2. 用数组表示堆这是重点如果用数组存index: 0 1 2 3 4 value: 9 6 8 5 4关系是左子节点 2*i 1 右子节点 2*i 2二、heapify核心操作到底在干嘛来看函数void heapify(vectorint arr, int i, int heapSize)作用一句话总结让以 i 为根的子树变成一个大顶堆具体做了什么int largest i; int left 2*i 1; int right 2*i 2;先找出当前节点左孩子右孩子然后找最大值if (left heapSize arr[left] arr[largest]) largest left; if (right heapSize arr[right] arr[largest]) largest right;如果最大值不是父节点swap(arr[i], arr[largest]); heapify(arr, largest, heapSize);这一步非常关键把“更大的那个”提上来然后继续往下调整举个例子原数组 [4, 6, 8, 5, 9]假设现在在 i04 / \ 6 8 / 5最大的是 8 → 交换8 / \ 6 4 / 5然后继续对 4 进行 heapify。三、第一步建堆最容易忽略的细节for (int i n / 2 - 1; i 0; --i) heapify(arr, i, n);为什么从 n/2 - 1 开始因为n/2 之后的节点全是叶子节点不需要调整这个过程在做什么从下往上把每个子树都变成大顶堆。最终效果整个数组变成一个大顶堆四、第二步排序过程for (int i n - 1; i 0; --i) { swap(arr[0], arr[i]); heapify(arr, 0, i); }每一轮发生了什么1. 把最大值放到最后swap(arr[0], arr[i]);因为堆顶是最大值。2. 缩小堆的范围heapify(arr, 0, i);只对前 i 个元素继续维护堆。举个完整过程初始[4, 6, 8, 5, 9]建堆后[9, 6, 8, 5, 4]第一轮swap → [4, 6, 8, 5, 9] heapify → [8, 6, 4, 5, 9]第二轮swap → [5, 6, 4, 8, 9] heapify → [6, 5, 4, 8, 9]继续下去最终结果 [4, 5, 6, 8, 9]五、复杂度分析建堆O(n)每次调整O(log n)总复杂度O(n log n)六、堆排序的特点优点不需要额外空间原地排序最坏情况也是 O(n log n)缺点不稳定排序常数略大比快排慢一点七、最容易犯的错误1. heapify 写错边界left heapSize right heapSize2. 忘记递归heapify(arr, largest, heapSize);3. 建堆起点写错n/2 - 1不是 n-1八、总结一句话堆排序的本质就是不断把“当前最大值”放到数组末尾排序过程再次重述假设数组[4, 6, 8, 5, 9]第一步建堆建完堆后数组变成大顶堆[9, 6, 8, 5, 4]对应树9 / \ 6 8 / \ 5 4堆顶 9 是最大值。第二步把最大值放到末尾swap(arr[0], arr[i]); i 4数组末尾 交换 9 和 4 [4, 6, 8, 5, 9]现在最后一位已经排好了9第三步调整剩余堆我们把“剩余堆”的长度设为 i 4然后对堆顶做 heapifyheapify(arr, 0, 4)根节点 4比它的两个子节点 6 和 8 小所以我们找到最大子节点 8交换交换 4 和 8 [8, 6, 4, 5, 9]然后继续对 4 的位置下沉做 heapify如果还有子节点比它大就再交换。这里 4 的子节点是 5比 4 大所以交换[8, 6, 5, 4, 9]剩余堆调整完毕最大值在堆顶8第四步重复上述操作下一轮 i 3交换堆顶 8 和末尾 4[4, 6, 5, 8, 9]对剩余堆 [4,6,5] heapify根 4比子节点 6 大小不对交换[6,4,5,8,9]根 4 下沉到叶子不需要调整了最终堆[6,4,5]第五步继续交换堆顶和末尾直到排序完成i2交换 6 和 5 → heapify → [5,4]i1交换 5 和 4 → heapify → [4]最终数组有序[4,5,6,8,9]核心理解每次把堆顶最大值放到末尾剩余部分继续维护大顶堆循环完成后整个数组就是升序排列所以排序阶段就是“不断提最大值 调整剩余堆”只要记住这一点heapSort 的流程就很直观了。