堆排序¶
一、什么是堆排序？¶
- 基于堆实现的排序算法
- 利用堆顶的有序性（最大值或最小值）来实现对数组的排序
二、为什么要用堆排序？¶
- 唯一能够同时最优地利用空间和时间的排序算法
- 缺点是很少和相邻元素比较，导致无法利用缓存
三、怎么实现堆排序？¶
堆排序可以分为 2 步：
- 构建堆：将数组构建成堆
- 堆排序：一直移除堆顶元素，直到堆为空为止
先将数据建成二叉树的形式，再进行排序。
3.1 构建堆¶
因为每次都是移除堆顶，而堆顶一直都是最大值/最小值，所以移除堆元素就是排序的过程。
比如说，数组 [2, 7, 1, 4, 3, 6, 5]，要从小到大排序。
第一步是构建堆，将数组构建出大顶堆的结构：
1=>6 7 2=>7=>4
2 2 2 7
/ \ / \ / \ / \
7 1 7 6 7 6 4 6
/ \ / \ / \ / \ / \ / \ / \ / \
4 3 6 5 4 3 1 5 4 3 1 5 2 3 1 5
构建完堆以后，数组变成了这样：
7
/ \
4 6 -- 逻辑结构（二叉树）
/ \ / \
2 3 1 5
___ ___ ___ ___ ___ ___ ___
| 7 | 4 | 6 | 2 | 3 | 1 | 5 | -- 物理结构（数组）
3.2 堆排序¶
接下来是排序，排序过程就是一直移除堆顶元素。
被移除的堆顶元素放到数组的末尾空位（相当于末尾已经不算在堆内了）：
7 6
/ \ / \
4 6 => 4 5
/ \ / \ / \ /
2 3 1 5 2 3 1
___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___
| 7 | 4 | 6 | 2 | 3 | 1 | 5 | | 6 | 4 | 5 | 2 | 3 | 1 | | 7 |
注意，移除堆顶的同时会调整堆结构（这个是堆的性质）。
以此类推，一直移除堆顶元素，直到堆变成空为止。
移除堆顶 6：
6 5
/ \ / \
4 5 => 4 1
/ \ / / \
2 3 1 2 3
___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___
| 6 | 4 | 5 | 2 | 3 | 1 | | 7 | | 5 | 4 | 1 | 2 | 3 | | 6 | 7 |
移除堆顶 5：
5 4
/ \ / \
4 1 => 3 1
/ \ /
2 3 2
___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___
| 5 | 4 | 1 | 2 | 3 | | 6 | 7 | | 4 | 3 | 1 | 2 | | 5 | 6 | 7 |
移除堆顶 4：
4 3
/ \ / \
3 1 => 2 1
/
2
___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___
| 4 | 3 | 1 | 2 | | 3 | 6 | 7 | | 3 | 2 | 1 | | 4 | 5 | 6 | 7 |
移除堆顶 3：
3 2
/ \ => \
2 1 1
___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___
| 3 | 2 | 1 | | 4 | 5 | 6 | 7 | | 2 | 1 | | 3 | 4 | 5 | 6 | 7 |
移除堆顶 2：
2 => 1
\
1
___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___
| 2 | 1 | | 3 | 4 | 5 | 6 | 7 | | 1 | | 2 | 3 | 4 | 5 | 6 | 7 |
至此，堆排序结束，数据已经排好序了。
四、算法分析¶
4.1 时间复杂度¶
- 最好时间复杂度：O(n)
- 最坏时间复杂度：O(nlogn)
- 平均时间复杂度：O(nlogn)
4.2 空间复杂度¶
- 空间复杂度：O(1)
- 原地算法
4.3 稳定性¶
- 不稳定排序算法
总结¶
- 基于堆实现的排序算法
- 利用堆顶的有序性（最大值或最小值）来实现对数组的排序
- 优缺点
- 优点：唯一能够同时最优地利用空间和时间的排序算法
- 缺点：很少和相邻元素比较，导致无法利用缓存
- 堆排序步骤
- 构建堆：将数组构建成堆
- 堆排序：一直移除堆顶元素，直到堆为空为止
参考¶
《算法（第4版）》
https://juejin.cn/post/7119807721766912030
附录¶
/**
* 堆排序
*
* @author weijiaduo
* @since 2023/2/26
*/
public class HeapSort implements Sort {
@Override
public void sort(int[] arr) {
// 建堆
int n = arr.length;
for (int i = (n - 1) / 2; i >= 0; i--) {
sink(arr, i, n);
}
// 排序
for (int i = n; i > 0; i--) {
swap(arr, 0, i - 1);
sink(arr, 0, i - 1);
}
}
/**
* 下沉
*
* @param arr 数组
* @param i 当前索引 i
* @param n 数组长度
*/
private void sink(int[] arr, int i, int n) {
while (i < n - 1) {
int m = i;
// 左子节点
int l = 2 * i + 1;
if (l < n && arr[l] > arr[m]) {
m = l;
}
// 右子节点
int r = 2 * i + 2;
if (r < n && arr[r] > arr[m]) {
m = r;
}
if (m == i) {
break;
}
swap(arr, i, m);
i = m;
}
}
}