939 字
5 分钟
【算法笔记】（八）堆结构和堆排序
堆结构与堆排序（Heap Structure & Heap Sort）
一、堆结构（Heap）
1. 什么是堆
堆（Heap）本质上是一种 完全二叉树（Complete Binary Tree）结构。
在实际实现中，堆通常 使用数组来存储，因为完全二叉树在数组中有天然的下标关系。
数组下标与树节点的关系如下：
| 节点 | 下标公式 |
|---|---|
| 父节点 | (i - 1) / 2 |
| 左孩子 | i * 2 + 1 |
| 右孩子 | i * 2 + 2 |
例如：
10 / \ 7 9 / \ / 3 4 8对应数组：
[10,7,9,3,4,8]2. 堆的调整操作
堆结构主要通过两种操作维护：
（1）heapInsert —— 向上调整
当新元素加入堆时，需要不断与父节点比较：
- 如果 比父节点大（大根堆），则交换
- 持续向上调整
- 直到不再大于父节点或到达根节点
时间复杂度：
O(log n)原因是完全二叉树的高度为 log n。
（2）heapify —— 向下调整
当某个节点变小后，需要向下调整：
步骤：
- 找到左右孩子中 较大的那个
- 与当前节点比较
- 如果孩子更大则交换
- 继续向下调整
时间复杂度：
O(log n)二、堆排序（Heap Sort）
堆排序是利用 堆结构的性质进行排序的一种算法。
核心思想：
- 先建立一个 大根堆
- 将堆顶（最大值）与数组最后一个元素交换
- 缩小堆范围
- 重新调整堆
- 重复直到排序完成
1. 建堆方式
A. 从顶到底建堆（heapInsert）
依次把元素插入堆中。
时间复杂度：
O(n * log n)B. 从底到顶建堆（heapify）
从最后一个节点开始向上进行 heapify。
时间复杂度：
O(n)这是 更优的建堆方式。
2. 排序阶段
建好堆之后：
- 交换堆顶和最后一个元素
- 堆大小减一
- 重新 heapify
时间复杂度：
O(n * log n)3. 空间复杂度
O(1)因为：
- 堆 直接建立在原数组上
- 不需要额外空间
4. 重要说明
在实际工程中：
堆结构本身比堆排序更重要
例如：
- 优先队列（PriorityQueue）
- TopK问题
- 调度系统
- 定时任务
尤其是 结合比较器（Comparator）之后，应用非常广泛。
三、Java实现
package org.example;
public class Main {
public static void main(String[] args) {
}
// i位置的数，向上调整大根堆 // arr[i]一直向上看，直到不比父亲大或者来到了顶部0位置才停止 public static void heapInsert(int[] arr, int i) { while (arr[i] > arr[(i - 1) / 2]) { //(0 - 1) / 2 = 0 ArrUtil.swap(arr, i, (i - 1) / 2); i = (i - 1) / 2; } }
// i位置的数变小后，向下调整大根堆 // 当前堆的大小为 size public static void heapify(int[] arr, int i, int size) {
int index = i * 2 + 1;
while (index < size) {
int big = index; // 先认为左孩子最大
if (index + 1 < size) { big = arr[index] > arr[index + 1] ? index : index + 1; }
// 比较当前节点和最大孩子 if (arr[i] < arr[big]) { ArrUtil.swap(arr, i, big); } else { break; }
i = big; index = 2 * big + 1; } }
// 从顶到底建立大根堆 // 依次弹出最大值并排序 public static void heapSort1(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) { heapInsert(arr, i); }
int size = n;
while (size > 1) { ArrUtil.swap(arr, 0, --size); heapify(arr, 0, size); } }
// 从底到顶建立大根堆 // 依次弹出最大值并排序 public static void heapSort2(int[] arr) {
int n = arr.length;
for (int i = n - 1; i >= 0; i--) { heapify(arr, i, n); }
int size = n;
while (size > 1) { ArrUtil.swap(arr, 0, --size); heapify(arr, 0, size); } }}四、时间复杂度总结
| 阶段 | 时间复杂度 |
|---|---|
| heapInsert | O(log n) |
| heapify | O(log n) |
| 建堆（heapInsert方式） | O(n log n) |
| 建堆（heapify方式） | O(n) |
| 排序阶段 | O(n log n) |
| 空间复杂度 | O(1) |
部分信息可能已经过时