堆排序核心是建堆和调整堆：先从最后一个非叶子节点（索引n/2−1）倒序heapify建大顶堆，再反复交换堆顶与末尾、缩小堆范围并heapify剩余部分完成升序排序。
堆排序的核心是建堆和调整堆
堆排序不是直接用 std::priority_queue 模拟，而是手动维护一个最大堆（或最小堆），再通过反复“弹出堆顶 + 重新调整”完成排序。关键动作只有两个：从最后一个非叶子节点开始向上 heapify（建堆），以及每次把堆顶与末尾交换后对剩余部分再次 heapify（排序轮次）。
常见错误是下标计算出错——C++ 数组从 0 开始，父节点索引为 (i-1)/2，左子节点为 2*i+1，右子节点为 2*i+2。写成 i/2 或 2*i 会导致越界或逻辑错乱。
- 建堆必须从最后一个非叶子节点倒序处理，不能从头开始：最后一个非叶子节点索引是
(n/2)-1（n为数组长度） -
heapify函数要递归或循环下沉，比较当前节点与左右子节点，选出最大值并交换，再对被交换的子树继续heapify - 排序阶段每次将
arr[0]（堆顶）与arr[i]（当前未排序区尾部）交换，然后只对arr[0..i-1]调用heapify
手写 heapify 时容易忽略边界检查
如果子节点索引超出数组范围，不加判断就访问 arr[left] 或 arr[right]，会触发未定义行为——尤其当数组长度为 1 或 2 时，right = 2*i+2 很可能越界。
正确做法是在比较前先确认索引有效性：
void heapify(vector<int>& arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
<pre class="brush:php;toolbar:false;">if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest); // 递归调整子树
}
}
注意：这里 n 是当前堆的大小（随排序推进不断减小），不是原始数组长度；i 是当前待调整节点下标。
原地排序要求交换逻辑严格匹配堆结构
堆排序必须原地进行，不能额外分配空间。这意味着所有操作都基于同一个 vector 或数组，而“已排序区”和“待排序堆区”是逻辑划分：每次交换后，末尾元素视为已确定位置，堆的有效长度减 1。
典型错误是循环变量范围写错：
- 建堆循环：从
i = n/2 - 1到i >= 0，步进为--i - 排序循环：从
i = n - 1到i > 0，每次执行swap(arr[0], arr[i])后调用heapify(arr, i, 0)（注意是i，不是n） - 漏掉
i > 0这个条件会导致对单元素堆调用heapify，虽无害但多余；更严重的是写成i >= 0会让最后一次交换把最小值又换回开头
性能和稳定性要注意什么
堆排序时间复杂度稳定为 O(n log n)，但常数因子比快排大；它不是稳定排序——相同元素的相对位置可能在 heapify 的多次交换中被改变。
实际使用中，除非明确需要最坏情况保障或内存受限，否则 std::sort（通常是混合排序）更快更安全。手写堆排序主要价值在于理解堆结构、练习下标推导和边界控制。
真正容易被忽略的点是：建堆过程本身是 O(n)，不是 O(n log n)——因为大部分节点在底层，下沉距离短。这个细节不影响实现，但若面试被问到时间复杂度推导，绕不开它。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
