【数据结构与算法】堆（大顶堆小顶堆堆排序）

‍ 关于作者会编程的土豆“不是因为看见希望才坚持而是坚持了才看见希望。”你好我是会编程的土豆一名热爱后端技术的Java学习者。正在更新中的专栏《数据结构与算法》《leetcode hot 100》作者简介后端学习者什么是堆排序大顶堆每个节点值 ≥ 子节点值。根节点最大。小顶堆每个节点值 ≤ 子节点值。根节点最小。用数组存储完全二叉树索引关系从0开始父节点i→ 左子2i1右子2i2子节点i→ 父节点⌊(i-1)/2⌋代码实现#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堆化/下沉这是堆排序的发动机。它的作用很专一当你有一个节点它的左右子树都已经是大顶堆了但唯独这个节点本身可能不满足堆的性质时Heapify能通过比较和交换把这个节点“下沉”到正确的位置从而让整棵树重新成为一个合法的大顶堆。具体步骤找出当前节点i、它的左子节点left和右子节点right三者中值最大的那个。如果最大的就是i自己那说明它已经在正确位置了操作结束。如果最大的不是i比如是左子节点那就把i和左子节点的值交换。交换后i原来的大值被移走了而换下来的小值可能又会破坏左子树的堆性质。所以我们需要递归地对发生交换的那个子节点再次执行Heapify直到整个子树都满足堆的性质。void heapify(std::vectorint arr, int n, int i) { int largest i; int left 2 * i 1; int right 2 * i 2; if (left n arr[left] arr[largest]) largest left; if (right n arr[right] arr[largest]) largest right; if (largest ! i) { std::swap(arr[i], arr[largest]); heapify(arr, n, largest); // 递归调整被影响的下层节点 } }说人话先从最底部开始比较左右节点及自己然后最大的换到根的位置然后继续比较换下来的节点的自身和他的左右还有继续向上比较先从最底部开始比较左右节点及自己然后最大的换到根的位置// 从最后一个非叶子节点开始自下而上 for (int i n / 2 - 1; i 0; --i) { heapify(arr, n, i); }向下比较下沉在heapify函数内部换下来的小值会递归地和它新位置的子节点比这是向下走。向上比较循环for循环的i--会处理上一个非叶子节点这是向上走面试里不会让你默写堆的定义而是什么看你能否识别出问题可以用堆来高效解决。Top K 问题在百万/亿级数据中找出最大/最小的 K 个元素。典型题目LeetCode 215. 数组中的第K个最大元素。思路求最大 K 个用小顶堆维持堆大小为 K遍历数据比堆顶大就替换并调整。数据流中的中位数数据源源不断到来随时能求出当前所有数据的中位数。典型题目LeetCode 295. 数据流的中位数。思路使用两个堆一个大顶堆存较小的一半一个小顶堆存较大的一半保持两个堆大小平衡。合并 K 个有序链表/数组典型题目LeetCode 23. 合并K个升序链表。思路用小顶堆维护每个链表当前的头部节点每次弹出最小值极大提升归并效率。带权图的最短路径典型题目Dijkstra 算法。思路用小顶堆作为优先队列每次高效取出当前距离起点最近且未确定最短路径的节点。