二叉堆的实现（上浮与下沉操作）
较难2堆的“上浮”与“下沉”——让数据自动排好队
同学们，你们有没有遇到过这样的场景：老师让全班同学按身高从矮到高排成一列，每次新来的同学要插入队列，或者最矮的同学被叫走后，队列需要重新调整。如果你想让最高（或最矮）的同学始终站在最前面、而且每次调整都尽量少移动人，你会怎么设计规则呢？其实，计算机里的二叉堆就用了特别聪明的两个操作——上浮（Sift Up）和下沉（Sift Down），来快速维护这种“老大在最前面”的队列。
二叉堆是一种特殊的完全二叉树，它用数组存数据，并且满足一个核心性质：每个节点的值都小于（或大于）它的子节点。按照这个性质，堆分为小根堆（最小值在根）和大根堆（最大值在根）。我们平时用的“优先队列”底层就是堆，而上浮和下沉就是堆里两个最基础、最核心的动作。掌握了它们，你就亲手实现了优先队列的核心！下面我们一起来拆解。
1. 堆的数组存储：把树藏进一排格子里
堆用数组存储时，下标从0开始。对于一个节点下标 i，它的亲人下标是固定的：
- 左孩子：
2 * i + 1 - 右孩子：
2 * i + 2 - 父节点：
(i - 1) // 2
例如下面这个小根堆，树形和数组对应关系一目了然：
树形：
3
/ \
5 7
/ \
8 9
数组下标：0→3, 1→5, 2→7, 3→8, 4→9
生活类比：你可以把数组想象成一条长长的排队通道，第0号位置是“老大”，后面依次是次子、孙子……想找到一个人，用公式直接算出他的孩子或爸爸的位置，就像用家谱图查亲戚一样方便。
2. 上浮操作（Sift Up）——新来的“插队者”往上升
上浮操作用在插入新元素的时候。设想你往已经排好的队伍后面加了个新人，这个新人如果比排在前面的人矮（小根堆），他就要不停往前“浮”，直到找到一个比他更矮的人挡在前面才停下。
步骤：
- 把新元素放到数组末尾（相当于完全二叉树最后一个位置）。
- 比较新元素和它的父节点：如果新元素更小（小根堆），就交换位置；否则停止。
- 继续往上比较，直到满足堆序或者到达根节点。
手动模拟：插入数字2到 [3,5,7,8,9]
初始树：
3
/ \
5 7
/ \
8 9
插入2到末尾，变成：
3
/ \
5 7
/ \ /
8 9 2
2比父节点7小，交换：
3
/ \
5 2
/ \ /
8 9 7
2比父节点3小，交换：
2
/ \
5 3
/ \ /
8 9 7
此时2是根，且满足小根堆（比两个子节点都小），上浮结束。
生活类比：想象班里按身高排队，最矮的站在最前面。新同学来了，站在队尾。如果发现他比前面的人矮，他就和前面的人换位置，一直往前换，直到遇到比他更矮的人为止。这就是“上浮”——把更小的元素往上推。
3. 下沉操作（Sift Down）——被提上来的“替补”往下降
下沉操作用在删除堆顶元素（也就是当前最小的元素）的时候。删除堆顶后，我们会把数组最后一个元素移到堆顶，这个“替补”可能比原来堆顶大很多，所以需要让它“沉”到合适的位置。
步骤：
- 把堆顶元素和最后一个元素交换，然后删除最后一个元素（这样就移除了原来的堆顶）。
- 新的堆顶元素（原末尾元素）与它的较小的子节点比较（小根堆）：如果它比子节点大，就交换；否则停止。
- 继续向下重复，直到满足堆序或到达叶子节点。
手动模拟：删除堆顶2（从 [2,5,3,8,9,7] 开始）
原始堆（小根堆）：
2
/ \
5 3
/ \ /
8 9 7
删除堆顶2：先把最后一个元素7移到堆顶，然后删除末尾（2已丢弃）：
7
/ \
5 3
/ \
8 9
现在7需要下沉：比较它的两个孩子5和3，较小的是3，7 > 3，交换7和3：
3
/ \
5 7
/ \
8 9
再次检查7：它的左孩子下标是2*2+1=5，对应数组只有5个元素（下标0~4），5越界，说明7没有孩子，下沉结束。
最终堆：
3
/ \
5 7
/ \
8 9
生活类比：班里最矮的同学被叫走了（比如转学），老师让队伍最后一个人顶替到第一个位置。这个顶替的人如果比后面的人高，他就和后面更矮的人交换位置，一直换到比他更矮的人挡不住他为止。这就是“下沉”——把较大的元素往下压。
4. 常见错误与避坑指南
初学堆操作时，很容易踩到下面几个坑，这里帮你提前排雷：
❌ 错误1：上浮时忘记检查父节点是否存在
上浮循环条件只写了 while true 或没有判断 index > 0，可能导致访问 heap[-1] 或无限循环。正确做法：循环条件一定要包含 index > 0，确保不是根节点。
❌ 错误2：下沉时只比较一个子节点
有些人只比较左孩子，或者只比较父节点与左孩子，没有考虑右孩子也可能更小。正确做法：先找出左右孩子中的较小者（小根堆），再和父节点比较。
❌ 错误3：下沉时忘记更新 smallest 为交换后的新下标
交换后，原来的父节点下沉到了子节点位置，需要把 index 更新为这个新位置，否则会陷入死循环或只沉一次。正确做法：交换后 index = smallest。
❌ 错误4：删除堆顶后，忘记判断堆是否为空就调用 siftDown
如果堆只有一个元素，删除后堆为空，再调用 siftDown(0) 会导致数组越界。正确做法：pop() 中先判断 heap 是否非空再调用 siftDown。
❌ 错误5：混淆小根堆和大根堆的比较方向
初学时常把上浮条件写成 heap[index] > heap[parent]（大根堆），但自己明明在实现小根堆。正确做法：先确定你要的是小根堆还是大根堆，然后统一比较符号。
5. 完整代码示例（C++和Python）
下面的代码展示了带注释的堆实现，变量名简短，每行都有中文注释，方便你阅读。
C++ 版本（带详细注释）
#include <iostream>
#include <vector>
using namespace std;
// 小根堆类
class BinaryHeap {
private:
vector<int> heap; // 存储堆元素的数组
// 上浮：从 index 位置向上调整
void siftUp(int index) {
while (index > 0) { // 不是根节点才需要比较
int parent = (index - 1) / 2; // 父节点下标
// 如果当前节点小于父节点，交换（小根堆）
if (heap[index] < heap[parent]) {
swap(heap[index], heap[parent]);
index = parent; // 继续向上
} else {
break; // 已经满足堆序，停止
}
}
}
// 下沉：从 index 位置向下调整
void siftDown(int index) {
int size = heap.size(); // 当前堆大小
while (true) {
int left = 2 * index + 1; // 左孩子下标
int right = 2 * index + 2; // 右孩子下标
int smallest = index; // 假设当前节点就是最小的
// 如果左孩子存在且小于当前最小节点，更新最小节点
if (left < size && heap[left] < heap[smallest]) {
smallest = left;
}
// 如果右孩子存在且小于当前最小节点，更新最小节点
if (right < size && heap[right] < heap[smallest]) {
smallest = right;
}
// 如果最小节点不是当前节点，则交换并继续下沉
if (smallest != index) {
swap(heap[index], heap[smallest]);
index = smallest; // 更新为交换后的下标
} else {
break; // 已经满足堆序，停止
}
}
}
public:
// 插入元素
void push(int val) {
heap.push_back(val); // 先加到最后
siftUp(heap.size() - 1); // 然后上浮
}
// 获取堆顶元素（不删除）
int top() const {
if (heap.empty()) throw runtime_error("堆为空");
return heap[0];
}
// 删除堆顶元素
void pop() {
if (heap.empty()) throw runtime_error("堆为空");
heap[0] = heap.back(); // 将最后一个元素移到堆顶
heap.pop_back(); // 删除最后一个元素
if (!heap.empty()) { // 如果堆不为空，下沉调整
siftDown(0);
}
}
// 打印堆的数组形式
void print() const {
for (int val : heap) {
cout << val << " ";
}
cout << endl;
}
bool empty() const { return heap.empty(); }
int size() const { return heap.size(); }
};
int main() {
BinaryHeap h;
cout << "依次插入：5,3,8,1,9,2" << endl;
h.push(5); h.print();
h.push(3); h.print();
h.push(8); h.print();
h.push(1); h.print();
h.push(9); h.print();
h.push(2); h.print();
cout << "依次弹出堆顶：" << endl;
while (!h.empty()) {
cout << "弹出 " << h.top() << "，剩余：";
h.pop();
h.print();
}
return 0;
}
Python 版本（带详细注释）
class BinaryHeap:
def __init__(self):
self.heap = [] # 存储堆元素的列表
def _sift_up(self, index):
"""从 index 开始向上调整"""
while index > 0: # 不是根节点才需要比较
parent = (index - 1) // 2 # 父节点下标
# 如果当前节点小于父节点，交换（小根堆）
if self.heap[index] < self.heap[parent]:
self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
index = parent # 继续向上
else:
break # 已经满足堆序
def _sift_down(self, index):
"""从 index 开始向下调整"""
size = len(self.heap)
while True:
left = 2 * index + 1
right = 2 * index + 2
smallest = index # 假设当前节点最小
# 如果左孩子存在且更小，更新 smallest
if left < size and self.heap[left] < self.heap[smallest]:
smallest = left
# 如果右孩子存在且更小，更新 smallest
if right < size and self.heap[right] < self.heap[smallest]:
smallest = right
# 如果最小节点不是当前节点，交换并继续下沉
if smallest != index:
self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
index = smallest # 更新为交换后的下标
else:
break
def push(self, val):
"""插入元素"""
self.heap.append(val) # 先加到最后
self._sift_up(len(self.heap) - 1) # 然后上浮
def top(self):
"""获取堆顶元素"""
if not self.heap:
raise Exception("堆为空")
return self.heap[0]
def pop(self):
"""删除堆顶元素"""
if not self.heap:
raise Exception("堆为空")
# 将最后一个元素移到堆顶
self.heap[0] = self.heap[-1]
self.heap.pop() # 删除最后一个元素
if self.heap: # 如果堆不为空，下沉调整
self._sift_down(0)
def print_heap(self):
print(self.heap)
def empty(self):
return len(self.heap) == 0
def size(self):
return len(self.heap)
# 测试
if __name__ == "__main__":
h = BinaryHeap()
print("依次插入：5,3,8,1,9,2")
h.push(5); h.print_heap()
h.push(3); h.print_heap()
h.push(8); h.print_heap()
h.push(1); h.print_heap()
h.push(9); h.print_heap()
h.push(2); h.print_heap()
print("依次弹出堆顶：")
while not h.empty():
print(f"弹出 {h.top()}，剩余：", end="")
h.pop()
h.print_heap()
6. 总结与进阶指引
回顾一下两个核心操作：
| 操作 | 使用场景 | 对比对象 | 方向 |
|---|---|---|---|
| 上浮 | 插入新元素 | 父节点 | 从下往上 |
| 下沉 | 删除堆顶 | 左右子节点中较小（或较大）的 | 从上往下 |
- 时间复杂度：上浮和下沉都是沿着树的高度移动，所以都是 O(log n)，其中 n 是堆的大小。
- 小根堆 vs 大根堆：代码中所有比较符号（
<）改成>就变成大根堆（最大值在根）。例如上浮条件改成if heap[index] > heap[parent]，下沉时找左右子节点中较大的那个。 - 堆的构建：如果想直接把一个无序数组建成堆，可以用“自底向下沉”的方法（时间复杂度 O(n)），这叫做 建堆（heapify），是上浮/下沉的高级应用。
相关知识点：
- 堆排序（利用堆实现排序）
- 优先队列（C++的
priority_queue，Python的heapq） - 合并有序小文件、求Top K问题、Dijkstra最短路径算法（都用到了堆）
- 二叉堆的变种：二叉堆的存储也可以从下标1开始（把0空出来），这时候孩子和父节点公式变为
左孩子=2*i，右孩子=2*i+1，父节点=i//2，更简洁，有些教材采用这种写法。
掌握了上浮和下沉，就像学会了堆的“呼吸”和“心跳”——后面所有的堆操作都离不开它们。赶快打开编辑器，亲手写一个自己的堆吧！
例题精讲
在构建一个大小为n的最小堆时，使用下沉操作（sift down）的初始节点通常是从哪个位置开始？
在最小堆中，如果某个节点的值小于其父节点的值，则需要对当前节点执行上浮操作（sift up）。
以下是一个最小堆的下沉操作（sift down）函数实现，请补全条件判断语句，使其能正确选择较小的子节点进行交换。\nvoid siftDown(vector<int>& heap, int idx, int size) {\n int smallest = idx;\n int left = 2 * idx + 1;\n int right = 2 * idx + 2;\n if (left < size && heap[left] < heap[smallest]) smallest = left;\n if (right < size && ___ ) smallest = right;\n if (smallest != idx) {\n swap(heap[smallest], heap[idx]);\n siftDown(heap, smallest, size);\n }\n}对一个含有n个元素的二叉堆执行一次上浮操作（sift up）的时间复杂度是多少？
在最大堆中，执行上浮操作时，如果当前节点的值大于其父节点的值，则需要交换两者并继续向上调整。