堆排序的核心思想
堆排序是一种基于完全二叉树结构的高效排序算法，利用“堆”这种数据结构来组织元素。堆的本质是一个数组，但逻辑上表现为一棵完全二叉树，其中每个父节点的值都不小于（或不大于）其子节点——前者叫大根堆，后者叫小根堆。
比如你在整理快递包裹时，总是把最重的放在最下面，轻的往上叠，这样每次取最上面那个就是当前最轻的。堆排序就像在不断调整这个“重量顺序”，让最大值依次沉到底部，最终完成整体排序。
堆的存储方式与索引关系
虽然堆是树形结构，但实际中用数组存储更省空间、效率更高。假设数组下标从0开始，那么对于任意位置 i 的节点：
- 它的左孩子在
2*i + 1 - 右孩子在
2*i + 2 - 父节点在
(i - 1) / 2
这种映射让遍历和调整变得简单直接，不需要额外指针开销。
构建大根堆的关键步骤
排序前先要把无序数组变成一个大根堆。做法是从最后一个非叶子节点开始，自底向上执行“下沉”操作（也叫 heapify）。所谓下沉，就是让当前节点和它的子节点比较，如果比某个子节点小，就交换位置，直到满足堆的性质。
这个过程就像开会排座位，领导必须坐在每一级小组的正中间位置，一旦发现下属级别更高，就得换位，直到整个组织层级清晰。
排序过程：逐个提取最大值
建好大根堆后，最大元素就在数组第一个位置。把它和最后一个元素交换，相当于把当前最大值“拎出来”放到正确位置。然后对剩下的元素重新调整堆，再取出新的最大值……如此反复，直到所有元素归位。
每轮操作都缩小待处理区间的长度，就像食堂打饭，每次把排头的人安排去吃饭，剩下的人重新按身高排队，高的继续站前头。
代码实现示例
下面是用 C++ 实现的堆排序完整代码：
void heapify(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]);
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}函数 heapify 负责维护堆结构，heapSort 先建堆再逐个输出最大值。时间复杂度稳定在 O(n log n)，适合大规模数据排序。
应用场景与优势
堆排序不像快排那样依赖分区策略，也不像归并需要额外空间，在内存紧张的嵌入式系统或底层系统软件中很实用。操作系统中的优先队列调度、任务管理器里的高优先级进程选取，背后都有类似机制在运行。
它原地排序、空间复杂度 O(1)，虽然现代编程语言大多封装了更易用的排序接口，但理解堆排序的实现，能帮你写出更高效的底层模块，也能在面试手撕代码时稳住阵脚。