医院的急诊科不排队：骨折的让位于心脏骤停的。这就是优先队列（Priority Queue）——不是按先来后到，而是按「优先级」出队 🏥。
🎫 优先队列 ADT
存储带优先级的元素（key, value），只支持三件事：
insert(k, v)：随意插，不管顺序；min()：看一眼最小（或最大）的；removeMin()：拿走最小的——谁 key 小谁先走。
🤔 最朴素的实现，都不完美
- 无序列表：insert 直接放末尾 O(1)，但 removeMin 得全表扫一遍 O(n)；
- 有序列表：removeMin 直接取头 O(1)，但 insert 得找位置 O(n)。
鱼和熊掌…有没有都要？有——堆（Heap）来了 ⛰️。
⛰️ 堆：两条规则立天下
- 堆序性质：每个节点的 key ≤ 它孩子的 key → 根永远是全局最小 ⭐；
- 完全二叉树：除了最后一层，全满；最后一层从左到右排——这让树高只有 O(log n)，而且可以用数组存放（节点 i 的孩子是 2i+1 和 2i+2，连指针都省了）💰。
插入：先塞门口，再「上浮」🫧
新元素先放到最后一个位置（保持完全二叉树形状），然后和父节点比：比父小就和父交换，一路往上冒——up-heap bubbling，最多走树高次，O(log n)。
删除最小：末尾顶上，再「下沉」⬇️
根是最小值，拿走它之后，把最后一个元素搬到根上补位，然后和两个孩子中较小的那个比：比孩子大就交换，一路往下沉——down-heap bubbling，同样 O(log n)。
🏗️ 建堆的魔法：自底向上 O(n)
把 n 个元素逐个 insert 建堆是 O(n log n)。但书里教了更快的套路：把 n 个元素随便塞进数组，从最后一个非叶节点开始，倒着逐个下沉——总代价经数学推导只有 O(n)！
原因很有意思：绝大多数节点在底层，它们下沉的距离很短。大多数节点只干一点点活，总功就是 O(n)。这是全书最优雅的分析案例之一 🌟。
🏆 堆排序：原地 O(n log n)
有了堆，排序免费送：把数组原地建成小顶堆 → 反复 removeMin（每次把最小值换到尾部）→ 完成时数组有序。时间 O(n log n)，空间 O(1)，无递归——三好学生，只是缓存不友好、不稳定。
🎯 本章通关清单
- [ ] 说出优先队列两种朴素实现各自的 O(1) 与 O(n)
- [ ] 数组里 i 位置的左右孩子下标是多少？
- [ ] 手动演示一次插入上浮和一次 removeMin 下沉
- [ ] 解释自底向上建堆为什么是 O(n)
能自动「选最小」的树有了。那任意 key 都能 O(log n) 查到呢？下一章——哈希表 🎩