二叉堆详解实现优先级队列
raw/articles/2026/05/二叉堆详解实现优先级队列.md
一句话总结
通过 swim（上浮）和 sink（下沉）两个核心操作维护堆性质，实现高效的优先级队列数据结构。
核心要点
1. 二叉堆的本质
二叉堆是一种特殊的完全二叉树，存储在数组中而非链式结构。通过数组索引计算父子关系：
- 父节点：
parent = root / 2 - 左子节点：
left = root * 2 - 右子节点：
right = root * 2 + 1
2. 堆性质
- 最大堆：每个节点都大于等于它的两个子节点，堆顶是最大元素
- 最小堆：每个节点都小于等于它的两个子节点，堆顶是最小元素
3. 两大核心操作
- swim（上浮）：当节点比父节点大时，交换位置向上浮动
- sink（下沉）：当节点比子节点小时，与较大的子节点交换向下沉
4. 优先级队列实现
基于二叉堆实现，核心 API：
insert(Key e)：插入到堆底，然后 swim 上浮到正确位置delMax()：堆顶与堆底交换，删除原堆顶，然后 sink 下沉恢复堆性质
基本原理
二叉堆通过数组存储完全二叉树，利用索引关系而非指针维护树结构。插入和删除时通过局部调整（上浮/下沉）维护堆性质，避免全局重建。
上浮代码（swim）：
private void swim(int k) {
while (k > 1 && less(parent(k), k)) {
exch(parent(k), k);
k = parent(k);
}
}
下沉代码（sink）：
private void sink(int k) {
while (left(k) <= N) {
int older = left(k);
if (right(k) <= N && less(older, right(k)))
older = right(k);
if (less(older, k)) break;
exch(k, older);
k = older;
}
}
| 概念 | 说明 |
|---|---|
| 完全二叉树 | 除最后一层外，所有层都满的二叉树 |
| 最大堆 | 父节点 ≥ 子节点的堆 |
| 最小堆 | 父节点 ≤ 子节点的堆 |
| 上浮/下沉 | 维护堆性质的局部调整操作 |
时间复杂度
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| insert | O(logK) | K 为堆中元素总数，最多上浮树高次 |
| delMax | O(logK) | 最多下沉树高次 |
| max | O(1) | 直接返回堆顶元素 |
代码实现
关键代码片段
public class MaxPQ<Key extends Comparable<Key>> {
private Key[] pq;
private int N = 0;
public MaxPQ(int cap) {
pq = (Key[]) new Comparable[cap + 1];
}
public void insert(Key e) {
N++;
pq[N] = e;
swim(N);
}
public Key delMax() {
Key max = pq[1];
exch(1, N);
pq[N] = null;
N--;
sink(1);
return max;
}
}
实现要点
- 数组索引 0 空着不用，从 1 开始存储，简化父子关系计算
- swim 和 sink 是互逆操作，但应用场景不同（插入用上浮，删除用下沉）
- 下沉时需要比较左右子节点，选择较大的进行交换
应用场景
- 堆排序（Heap Sort）
- 优先级队列（Priority Queue）
- 任务调度系统
- Dijkstra 等图算法中的优先队列优化
- TopK 问题（维护大小为 K 的堆）
相关概念
相关实体
- labuladong：本文作者，算法博主
- 博客园：文章发布平台，暂不创建独立页
总结
二叉堆是一种简单而强大的数据结构，通过 swim 和 sink 两个操作（代码仅十行）就能维护堆性质，进而实现高效的优先级队列。其巧妙之处在于用数组存储完全二叉树，通过索引计算而非指针维护父子关系，体现了数据结构设计的精妙。