Heaps / Priority Queues
堆 / 优先队列
~ 16 min · v15
堆 / 优先队列
cs-ds/heap · COMP25211 一句话定义
堆（heap）专门解决一个问题：反复又快又省事地拿出"当前最大的那个"。它靠一条极简单的规则做到——每个父节点都 ≥ 它的孩子，于是根永远是全场最大，随手就能取走。
（把规则反过来——父 ≤ 子——就是最小堆，根是最小值。本节统一讲最大堆。）
2 模型 · 看堆怎么"上浮"和"下沉"
这一节分三小步，来：第 1 步先弄明白"数组怎么就成了树"；第 2 步看它在代码里怎么写；第 3 步再看堆被插入 / 删除打乱后，怎么靠"上浮 / 下沉"把自己修回来。
堆是完全二叉树——一层一层、从左到右填满，中间不留洞。正因为没有洞，把节点按"从上到下、从左到右"编号 0,1,2,…，就能一个不漏地塞进数组。编完号会冒出一个规律：谁的孩子都在 2i+1 和 2i+2。下面点任意一个节点或格子，看它的父亲、孩子分别落在哪个下标
试着点几个不同的格子，你会发现：越往下下标越大，但父子永远差着 2 倍左右的距离。这就是堆能用纯数组、不用任何指针的原因——"亲戚"全靠这三个算式现算。
不需要 struct、不需要指针——一个数组 h[] 加一个当前大小 n
就是一个堆。父子关系全靠下标算。下面这段建出的，正是上面那个示例堆。
// ① 一个堆 = 一个数组 + 当前元素个数 n（完全二叉树，无需指针） int h[100]; int n = 0; // ② 下标关系：靠算术算出"亲戚"，不用任何指针 // 父亲(i) = (i - 1) / 2 // 左孩子(i) = 2*i + 1 // 右孩子(i) = 2*i + 2 // ③ 把示例堆装进去（已满足"父 ≥ 子"，所以它就是合法最大堆） int init[] = { 90, 70, 80, 40, 60, 30, 75 }; for (int i = 0; i < 7; i++) h[n++] = init[i]; // h[0]=90 是根（最大）；h[1]=70、h[2]=80 是它的两个孩子……
对照上面的图：h[0]=90
是塔尖（最大）；h[1]、h[2]（70、80）是它的左右孩子；h[3..6] 是更下面一层。想知道谁是
h[6]=75 的父亲？算 (6-1)/2 = 2 → 就是 h[2]=80。下面就点 ▶
插入 / ▶ 删除堆顶，看上浮、下沉怎么一步步修复堆。
第 3 步 · 看堆怎么自我修复。堆只需要两个动作：插入时把新人放末尾、和父亲比着往上浮；删除堆顶时把末尾搬上来、和较大的孩子比着往下沉。关键直觉是——每次只有一个地方会违反"父≥子"，你只是把这个"违反点"沿着一条路一路推走。每一步我都会标出违反点在哪、这次交换怎么修。点 ▶ 慢慢看（先点插入/删除，再点播放）。
堆操作演示（数组 ↔ 树 同步）
父 = (i−1)/2 · 左孩子 = 2i+1 · 右孩子 =
2i+2
3 核心要点 · 4 句人话看懂堆
每张卡片先用一句大白话说清"它到底在讲什么"，再配最小例子。第 ① 条是堆的灵魂，记牢"只管父子、不管全局"。
h[1] 比 h[2]
大，也不能指望 h[3] 比 h[2] 小。最小堆则把规则反过来：父 ≤ 子，根是最小值。4 错误实验室 · 点一下亲眼看 bug
下面 4 个是写堆最常翻车的坑——第 ① 个是考试爱考的"建堆复杂度"误区，后 3 个是 sift-down 与下标的经典错误。点击卡片，控制台会模拟运行效果。
5 即时小测 · 5 题 + 动手例题
这 5 题都卡在初学者最常错的点上——堆性质（不是全局有序）、下标算术、上浮/下沉的落点、删堆顶后谁上位、以及优先队列的选型。点错也别灰心，提示会告诉你错在哪。最后到练习系统亲手把上浮写出来。
读完这节，你应该明白：
堆 = 完全二叉树 + "父 ≥ 子"一条规则 + 用数组存。这条规则很弱（兄弟、隔代都不保证顺序），所以堆不是排好序的，但它足以让根永远是最大值。维护它只需两招：插入时新人放末尾、和父亲比着上浮；删堆顶时末尾搬上来、和较大的孩子比着下沉——两招都只走"一条到根/到底的路"，长度 = 树高 ≈ log n，所以 insert 和 delMax 都是 O(log n)，取最大是 O(1)。正因如此，要反复"取当前极值"就用堆，这就是优先队列，也是堆排序、Dijkstra 的引擎 ↓