一、堆排序核心知识点
1. 底层基础
- 基于完全二叉树，用数组顺序存储
- 下标规则（从 0 开始）：
- 父节点：\((i-1)/2\)
- 左孩子：\(2i+1\)
- 右孩子：\(2i+2\)
- 堆分两种：
- 大根堆：父 ≥ 孩子 → 升序排序用
- 小根堆：父 ≤ 孩子 → 降序 / TopK 用
2. 核心思想
- 把原数组原地构建成大根堆
- 堆顶（最大值）和末尾元素交换，最大值落到有序末尾
- 缩小堆范围，对新堆顶做向下调整（堆化）
- 重复交换 + 堆化，直到整体有序
3. 复杂度
- 时间：平均 / 最好 / 最坏都是 \(O(n\log n)\)
- 空间：\(O(1)\) 原地排序，仅常数临时变量
- 稳定性：不稳定排序
4. 关键概念
- 堆化 shiftDown：某节点不满足堆性质，向下逐层调整
- 建堆：从最后一个非叶子节点倒着往前逐个堆化最后一个非叶子节点下标：\(n/2 - 1\)
5. 特点 & 面试考点
- 不受初始序列影响，稳定保持 \(O(n\log n)\)
- 原地排序，不额外开数组
- 不稳定，相同元素相对位置会变
- 适合海量数据 TopK、海量排序
- 缺点：缓存局部性不如快排，常数略大
6. 优化点
- 建堆从后往前非叶子节点开始，不用处理叶子
- 排序每次只堆化堆顶，不用重新建堆
二、堆排序完整源码（C++ 升序 大根堆）
cpp
#include <iostream> #include <vector> #include <algorithm> using namespace std; // 向下堆化：把以 idx 为根的子树调成大根堆 void shiftDown(vector<int>& arr, int idx, int len) { int parent = idx; int child = 2 * parent + 1; // 左孩子 while (child < len) { // 选左右孩子中更大的 if (child + 1 < len && arr[child + 1] > arr[child]) child++; if (arr[parent] >= arr[child]) break; // 已经满足大根堆，无需调整 swap(arr[parent], arr[child]); parent = child; child = 2 * parent + 1; } } // 堆排序主逻辑 void heapSort(vector<int>& arr) { int n = arr.size(); // 1. 建大根堆：从最后一个非叶子节点往前堆化 for (int i = n / 2 - 1; i >= 0; --i) { shiftDown(arr, i, n); } // 2. 依次交换堆顶到末尾 + 重新堆化 for (int i = n - 1; i > 0; --i) { swap(arr[0], arr[i]); // 堆顶最大值放末尾 shiftDown(arr, 0, i); // 缩小范围，调整堆顶 } } int main() { vector<int> arr = {4, 6, 8, 5, 9, 1, 3, 2, 7}; heapSort(arr); for (int x : arr) cout << x << " "; return 0; }三、小根堆版本（降序排序）
只改shiftDown比较逻辑即可：
cpp
void shiftDownMin(vector<int>& arr, int idx, int len) { int parent = idx; int child = 2 * parent + 1; while (child < len) { if (child + 1 < len && arr[child + 1] < arr[child]) child++; if (arr[parent] <= arr[child]) break; swap(arr[parent], arr[child]); parent = child; child = 2 * parent + 1; } } void heapSortDesc(vector<int>& arr) { int n = arr.size(); for (int i = n / 2 - 1; i >= 0; --i) shiftDownMin(arr, i, n); for (int i = n - 1; i > 0; --i) { swap(arr[0], arr[i]); shiftDownMin(arr, 0, i); } }
