实现优先队列时，堆和平衡树应该怎么选？
简化版
如果只关心「插入元素、取最大或最小、删除堆顶」，堆通常更合适。
如果还需要有序遍历、删除任意元素、查找前驱后继、同时访问最大和最小，平衡树更灵活。
堆是更专注的优先队列结构，平衡树是更通用的有序集合结构。
详细版
堆和平衡树都能实现优先队列，但它们擅长的问题不同。
| 操作 | 堆 | 平衡树 |
|---|---|---|
| 插入 | O(log n) | O(log n) |
| 查看最小值 | O(1) | O(log n) 或 O(1) 取决于实现 |
| 删除最小值 | O(log n) | O(log n) |
| 删除任意元素 | 不擅长 | O(log n) |
| 有序遍历 | 不擅长 | 擅长 |
| 前驱后继 | 不擅长 | 擅长 |
所以普通任务队列、Top K、堆排序更适合堆；需要按顺序遍历、范围查询、动态删除任意元素时更适合平衡树。
完整版教学
1. 两者都能做优先队列，但目标不同
堆的目标很单一：快速维护当前优先级最高的元素。
平衡树的目标更广：维护一组有序元素，并支持查找、插入、删除、遍历、前驱后继等操作。
这就决定了它们虽然都能实现优先队列，但不是同一种取舍。
面试里不要只背复杂度，要说清楚「操作需求」决定结构选择。
2. 堆为什么更适合纯优先队列
以小顶堆为例，最小元素永远在根节点。
因此：
- 查看最小值只需要访问
heap[0]； - 删除最小值只需要把最后一个元素移到根，再下沉；
- 插入元素只需要放到数组末尾，再上浮。
offer(x): append x, siftUp
peek(): heap[0]
poll(): swap root with last, remove last, siftDown这些操作都非常贴合数组结构，常数小、缓存友好。
3. 堆为什么不擅长删除任意元素
堆只保证父子之间的局部有序，不保证整棵树中序有序。
比如小顶堆中，根一定最小，但第 4 小的元素可能出现在很多位置。
如果要删除值为 x 的元素，普通堆通常要：
- 扫描数组找到
x； - 用最后一个元素替换它；
- 再上浮或下沉修复堆。
第一步就是 O(n)。
4. 平衡树为什么更灵活
平衡树维护全局有序关系。
因此它可以支持：
| 能力 | 说明 |
|---|---|
| 删除任意元素 | 先查找再删除，O(log n) |
| 前驱后继 | 很适合有序集合问题 |
| 范围遍历 | 可以从某个下界开始顺序扫描 |
| 同时访问最大最小 | 树的两端都可定位 |
例如 Java 的 TreeSet、C++ 的 set 都属于这类思想。
5. 常数和内存局部性也很重要
从大 O 看，插入和删除最值都是 O(log n)，似乎两者差不多。
但工程性能还取决于常数：
- 堆用数组，内存连续，缓存友好；
- 平衡树常用节点和指针，内存分散；
- 平衡树维护旋转和颜色等信息，逻辑更复杂；
- 堆的比较路径通常更简单。
所以在纯优先队列场景中，堆往往更快。
6. 重复元素怎么处理
优先队列通常天然允许重复元素。
平衡树如果是集合结构，可能不允许重复值，需要额外处理：
(priority, uniqueId)或者维护计数：
| 做法 | 说明 |
|---|---|
| priority + id | 每个元素唯一，排序稳定 |
| value -> count | 适合多重集合 |
| TreeMap | key 存值，value 存出现次数 |
这也是面试里可以补充的工程细节。
7. 怎么做选择题
可以直接按需求选：
| 需求 | 推荐 |
|---|---|
| Top K | 堆 |
| 任务调度只取最近任务 | 堆 |
| 数据流第 K 大 | 堆 |
| 滑动窗口删除过期元素 | 平衡树或双堆懒删除 |
| 需要范围查询 | 平衡树 |
| 需要前驱后继 | 平衡树 |
如果题目只说「每次取最小」，堆是默认答案；如果题目说「任意删除、范围、有序遍历」，就要想到平衡树。
8. 常见误区与追问
- 误区：堆和平衡树复杂度一样，所以随便选。 大 O 只是表层，常数、内存局部性和支持操作差异很大。
- 误区：堆是完全有序的。 堆只保证父子局部有序，不能直接有序遍历。
- 误区：平衡树一定比堆慢。 对纯优先队列通常堆更快，但对删除任意元素和范围查询，平衡树更合适。
- 追问：为什么滑动窗口最大值有时不用堆？ 因为堆删除过期元素麻烦，单调队列或平衡树可能更直接。
- 追问：如何让平衡树支持重复优先级？ 可以加入唯一 id 作为第二排序字段，或用计数 map 实现多重集合。