最大堆是一棵完全二叉树，它要求每个父节点的值都不小于其左右子节点的值。用数组来表示这棵树时，下标从0开始的话，节点i的左子节点位于2*i+1，右子节点位于2*i+2，父节点则位于(i-1)/2。这种紧凑的存储方式让堆操作不需要指针，直接在连续内存上就能完成。而向下调整算法是整个堆结构里最核心的动作，建堆和堆排序都离不开它。
最大堆的性质与向下调整的底层思路
向下调整通常被命名为maxHeapify、siftDown或者adjustHeap，名字不同，逻辑一致。它的前置条件是：当前节点i的左右子树都已经是合法最大堆，但节点i本身可能比子节点小。这种情况下，只需要比较节点i、左子节点和右子节点三者的值，找出最大值所在的位置。如果最大值不是节点i，就把节点i与较大的子节点交换。
交换之后，问题会转移到被交换的那个子节点上。因为原来的节点i下沉后，它所在的子树受到破坏，需要继续用同样的方式向下修复。这个过程会一直持续到节点不再小于子节点，或者已经到达叶子节点。由于完全二叉树的高度是log n级别，单次向下调整的时间复杂度就是O(log n)。
有一点需要特别注意：比较左右子节点之前，必须先判断下标是否越界。比如节点i可能没有右子节点，甚至没有左子节点。判断条件要写成left < n和right < n，其中n是当前堆的有效大小。有效大小在堆排序过程中会不断缩小，这一点后面会再次提到。
建堆的两种路径与复杂度差异
把任意数组整理成最大堆有两种常见方式。第一种是从空堆开始，逐个读取数组元素并执行上浮插入，每次插入最坏需要O(log n)，n个元素就是O(n log n)。第二种是从最后一个非叶子节点开始，依次向前对每个节点执行向下调整。最后一个非叶子节点的下标是n/2-1，从它开始一直调整到根节点，就能让整棵树满足最大堆性质。
第二种方式更高效，但它的正确性需要一点解释。为什么从n/2-1往前调整就够了？因为叶子节点本身已经是一个规模为1的堆，而向下调整要求左右子树先满足堆条件。当我们从后往前处理时，处理节点i时，它的左右子节点下标都大于i，这些节点要么是叶子，要么已经在之前的遍历中被调整过了。于是每次调用maxHeapify时，前置条件都成立。
关于复杂度，自下而上建堆的总代价是O(n)而不是O(n log n)。这个结论可以从两个角度理解。粗略地说，堆中下层节点数量多，但下层节点向下调整的距离短；上层节点数量少，但调整距离长。把每一层的节点数量和移动高度相乘后求和，结果趋近于n。更严格的计算会得到总交换次数不超过2n，因此建堆是线性时间。
下面是建堆的C++实现，采用了递归形式的向下调整：
#include <iostream>
#include <vector>
using namespace std;
void maxHeapify(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) {
swap(arr[i], arr[largest]);
maxHeapify(arr, n, largest);
}
}
void buildMaxHeap(vector<int>& arr) {
int n = arr.size();
for (int i = n / 2 - 1; i >= 0; --i) {
maxHeapify(arr, n, i);
}
}
这段代码中，maxHeapify的第三个参数i表示当前要下沉的节点。largest先设为i，然后分别尝试用左子节点和右子节点更新它。如果最终largest不等于i，说明父节点违反了堆性质，交换后继续递归调整。递归深度不会超过堆的高度，在实际使用中栈开销可以接受。
堆排序的执行流程与源码拆解
堆排序的核心思想是反复利用堆顶元素必定是最大值这一特性。建好最大堆之后，数组的第一个元素就是全局最大值。把它与当前堆的最后一个元素交换，最大值就落到了数组末尾的正确位置。交换之后，堆的有效大小减一，原来末尾的元素跑到了根节点，可能破坏堆结构，于是对根节点执行一次向下调整，重新恢复最大堆。
这个过程不断重复：交换堆顶与末尾，缩小堆，调整根节点。当堆的有效大小只剩1时，所有元素都已经交换到了正确位置，排序完成。需要注意循环的终止条件，当i大于0时继续，i等于0时说明堆里只剩一个元素，必然是最小值，已经在正确位置。
下面把建堆和堆排序串起来，给出完整的可运行代码：
#include <iostream>
#include <vector>
using namespace std;
void maxHeapify(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) {
swap(arr[i], arr[largest]);
maxHeapify(arr, n, largest);
}
}
void buildMaxHeap(vector<int>& arr) {
int n = arr.size();
for (int i = n / 2 - 1; i >= 0; --i) {
maxHeapify(arr, n, i);
}
}
void heapSort(vector<int>& arr) {
int n = arr.size();
buildMaxHeap(arr);
for (int i = n - 1; i > 0; --i) {
swap(arr[0], arr[i]);
maxHeapify(arr, i, 0);
}
}
int main() {
vector<int> data = {4, 10, 3, 5, 1, 7, 8, 2};
heapSort(data);
for (int v : data) {
cout << v << ' ';
}
return 0;
}
以数组{4, 10, 3, 5, 1, 7, 8, 2}为例，建堆完成后根节点是10。第一次交换把10放到最后，数组变成{2, 8, 7, 5, 1, 4, 3, 10}，然后对前7个元素从根开始向下调整，根节点2会下沉到合适位置。下一次循环处理前7个元素，堆顶变成8，再交换到倒数第二个位置。这样每次都会把当前最大值送到已排序区域。
堆排序不需要额外数组，空间复杂度为O(1)，平均和最坏时间复杂度都是O(n log n)。但由于堆的向下调整需要频繁跳跃访问数组元素，缓存局部性不如快速排序和归并排序，所以实际工程中纯堆排序使用较少，不过它的思想在优先队列、Top K问题中应用非常广泛。
边界场景与工程实践中的注意点
实现向下调整时，最容易出错的不是交换逻辑，而是下标越界和重复比较。比如在判断左右子节点时，如果只写arr[left] > arr[largest]而忘记检查left < n，就可能在堆大小缩小后访问到已经不属于堆的元素。堆排序循环里调用maxHeapify(arr, i, 0)时，第二个参数是逐渐减小的i，这个i控制了有效堆范围，必须确保调整函数所有判断都基于这个动态的n。
递归版向下调整在小规模数据上很清晰，但递归调用有函数栈开销。如果希望完全避免栈溢出风险，可以改成迭代写法。迭代版本不需要递归，只需要一个while循环，在当前节点不满足条件时持续下沉。下面给出迭代实现的maxHeapify：
void maxHeapifyIterative(vector<int>& arr, int n, int i) {
while (true) {
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) {
break;
}
swap(arr[i], arr[largest]);
i = largest;
}
}
这里用while (true)配合break实现下沉循环。每次迭代重新计算largest，如果largest没有变化，说明当前节点已经满足堆性质，直接跳出。否则交换，并把i更新为largest，继续向下检查。这种方式逻辑上与递归等价，但更节省栈空间。
另一个值得注意的问题是重复元素。最大堆的定义通常允许父节点等于子节点，因此判断条件使用>而不是>=。如果写成>=，遇到相等元素时会发生不必要的交换，虽然不影响最终排序结果，但会降低效率。堆排序本身不是稳定排序，因为交换堆顶和末尾时，相等的元素相对顺序可能被破坏。
在实际编码中，如果你需要频繁取出最大值而不是一次性排序，应该直接使用标准库中的priority_queue。但理解底层向下调整算法，对处理自定义堆结构、实现高效的Top K筛选、以及应对面试中的手写堆排序题目都很有帮助。掌握了从最后一个非叶子节点建堆和交换后下沉这两个核心过程，最大堆相关的代码基本就不会再被细节卡住。