堆排序
一句话总结
堆排序是基于二叉堆结构的原地排序算法，复杂度为 O(N log N)，通过原地建堆（Heapify）和排序两个步骤完成。
核心要点
1. 堆排序的两个关键步骤
原地建堆（Heapify）：直接把待排序数组原地变成一个二叉堆。
排序（Sort）：将元素不断地从堆中取出，最终得到有序的结果。
2. 堆排序与优先级队列的关系
最简单的堆排序思路是直接利用优先级队列：把所有元素塞到优先级队列里面，然后再取出来。但这种方法空间复杂度是 O(N)，因为需要额外的数据结构。
堆排序解决的问题是：不要使用额外的辅助空间，直接在原数组上进行 sink, swim 操作，在 O(N log N) 的时间内完成排序。
3. 二叉堆的关键原理
- 二叉堆（优先级队列）底层是用数组实现的，但是逻辑上是一棵完全二叉树，主要依靠
swim, sink方法来维护堆的性质。 - 优先级队列可以分为小顶堆和大顶堆，小顶堆会将整个堆中最小的元素维护在堆顶，大顶堆会将整个堆中最大的元素维护在堆顶。
- 优先级队列插入元素时，首先把元素追加到二叉堆底部，然后调用
swim方法把该元素上浮到合适的位置，时间复杂度是 O(log N)。 - 优先级队列删除堆顶元素时，首先把堆底的最后一个元素交换到堆顶作为新的堆顶元素，然后调用
sink方法把这个新的堆顶元素下沉到合适的位置，时间复杂度是 O(log N)。
基本原理
堆排序基于二叉堆结构，通过 swim（上浮）和 sink（下沉）操作维护堆性质。
利用优先级队列的简单实现思路：
// 直接利用优先级队列对数组从小到大排序
void sort(int[] nums) {
// 创建一个从小到大排序元素的小顶堆
SimpleMinPQ pq = new SimpleMinPQ(nums.length);
// 先把所有元素插入到优先级队列中
for (int num : nums) {
// push 操作会自动构建二叉堆，时间复杂度为 O(logN)
pq.push(num);
}
// 再把所有元素取出来，就是从小到大排序的结果
for (int i = 0; i < nums.length; i++) {
// pop 操作从堆顶弹出二叉堆堆中最小的元素，时间复杂度为 O(logN)
nums[i] = pq.pop();
}
}
因为优先级队列的 push, pop 方法的复杂度都是 O(log N)，所以整个排序的时间复杂度是 O(N log N)。
原地堆排序（真正的堆排序）需要：
- 原地建堆：直接在原数组上进行 sink/swim 操作
- 原地排序：将堆顶元素（最大或最小）与堆底元素交换，然后缩小堆的范围并调整
| 概念 | 说明 |
|---|---|
| 二叉堆 | 逻辑上是完全二叉树，物理上是数组实现 |
| 小顶堆 | 堆顶元素是最小值，用于升序排序 |
| 大顶堆 | 堆顶元素是最大值，用于降序排序 |
| swim | 元素上浮，用于插入元素后调整 |
| sink | 元素下沉，用于删除堆顶后调整 |
| Heapify | 原地建堆过程，将无序数组调整为堆 |
时间复杂度
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 建堆（Heapify） | O(N) | 从最后一个非叶子节点开始 sink |
| 排序（每次取堆顶） | O(log N) | 每次 sink 操作 |
| 总排序时间 | O(N log N) | N 个元素，每个 O(log N) |
| 空间复杂度 | O(1) | 原地排序，不需要额外空间 |
代码实现
关键代码片段
文章提到了二叉堆的 swim, sink 方法（从优先级队列实现中提取）：
// swim 操作：元素上浮
void swim(int[] heap, int k) {
while (k > 1 && less(heap, k/2, k)) {
swap(heap, k/2, k);
k = k/2;
}
}
// sink 操作：元素下沉
void sink(int[] heap, int k, int N) {
while (2*k <= N) {
int j = 2*k;
if (j < N && less(heap, j, j+1)) j++;
if (!less(heap, k, j)) break;
swap(heap, k, j);
k = j;
}
}
实现要点
- 堆排序必须掌握二叉堆结构原理，否则无法理解排序过程
- 学习堆排序算法可以使用算法可视化工具观察建堆和排序过程
- 原地建堆是从最后一个非叶子节点开始，向前遍历进行 sink 操作
- 排序时，将堆顶元素与堆尾元素交换，然后对新的堆顶进行 sink 操作
对比分析
| 维度 | 堆排序 | 快速排序 | 归并排序 |
|---|---|---|---|
| 时间复杂度 | O(N log N) | 平均 O(N log N)，最坏 O(N²) | O(N log N) |
| 空间复杂度 | O(1) | O(log N) 递归栈 | O(N) |
| 稳定性 | 不稳定 | 不稳定 | 稳定 |
| 原地排序 | 是 | 是 | 否 |
应用场景
- 需要 O(N log N) 时间复杂度且空间受限的场景
- 实现优先级队列的基础（虽然本文提到用优先级队列实现排序会额外占用空间）
- 内省排序（IntroSort）的组成部分：C++ 的
std::sort结合快速排序、堆排序、插入排序
相关题目
| 平台 | 题目 | 难度 |
|---|---|---|
| LeetCode | 912. Sort an Array | 中等 |
| 力扣 | 912. 排序数组 | 中等 |
相关概念
- 堆排序：基于二叉堆的原地排序算法，O(N log N)时间复杂度
- 二叉堆：完全二叉树结构，支持 sink/swim 操作维护堆性质
- 优先级队列：基于二叉堆实现，支持按优先级取出元素
- 排序算法：各种排序算法的分类与对比
- 时间复杂度：O(N log N) 的分析
- 原地排序：不需要额外 O(N) 空间的排序方法
相关实体
- labuladong：本文作者，算法学习平台
总结
堆排序是基于二叉堆结构的优雅排序算法，通过原地建堆和排序两个步骤实现 O(N log N) 时间复杂度、O(1) 空间复杂度的原地排序。掌握二叉堆的 sink/swim 操作是理解堆排序的关键。
待补充
由于原文通过 defuddle 提取时可能不完整（输出仅有75行，以"Loading comments..."结尾），以下内容可能缺失：
- 完整的原地堆排序代码实现
- 建堆（Heapify）的详细步骤和图解
- 排序（Sort）的详细步骤和图解
- 完整的优化过程和代码演进
如需完整内容，请手动复制原文后重新摄取。