【数据结构与算法】堆（大顶堆小顶堆堆排序）
👨💻 关于作者：会编程的土豆
“不是因为看见希望才坚持，而是坚持了才看见希望。”
你好，我是会编程的土豆，一名热爱后端技术的Java学习者。
📚正在更新中的专栏：
《数据结构与算法》
《leetcode hot 100》
💕作者简介：后端学习者
什么是堆排序
大顶堆：每个节点值 ≥ 子节点值。根节点最大。
小顶堆：每个节点值 ≤ 子节点值。根节点最小。
用数组存储完全二叉树，索引关系（从0开始）：
父节点
i→ 左子2i+1，右子2i+2子节点
i→ 父节点⌊(i-1)/2⌋
代码实现：
#include <iostream> #include <vector> using namespace std; // 下沉调整：维护大顶堆性质 void heapify(vector<int>& 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(vector<int>& 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() { vector<int> 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::vector<int>& 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 算法。
思路：用小顶堆作为优先队列，每次高效取出当前距离起点最近且未确定最短路径的节点。