学习笔记19 10 月, 2026· 约 4 分钟
优先队列与最小堆
优先队列与最小堆 一、核心结论 SortedDictionary<TKey,TValue 不能直接当优先队列用,不推荐。 .NET 6+ 官方提供 PriorityQueue<TElement,TPriority ,底层是最小堆。 二、为什么 SortedDictionary 不合适 SortedDictionary
优先队列与最小堆
一、核心结论
SortedDictionary<TKey,TValue> 不能直接当优先队列用,不推荐。
.NET 6+ 官方提供 PriorityQueue<TElement,TPriority>,底层是最小堆。
二、为什么 SortedDictionary 不合适
SortedDictionary 底层是红黑树,两个硬伤:
- Key 必须唯一,无法直接存放多个相同优先级的任务。补救方案是用复合键
(优先级, 自增序号)。 - 它要维护全集有序,而优先队列只需要保证堆顶最小,红黑树多做了一大堆无用功。
性能对比
SortedDictionary的 Add/Remove:O(log n),红黑树常数开销大;PriorityQueue的 Enqueue/Dequeue:O(log n),堆的内存开销更小。
Unity 版本适配
- Unity 2023.2+(.NET 7 运行时)可直接用原生
PriorityQueue; - 低版本 Unity 没有这个 API,需要手写最小堆。
三、手写最小堆的原理
底层用 List 实现,满足"父节点 ≤ 两个子节点",左右子节点之间没有大小约束。
下标关系:
- 父索引:
(idx - 1) / 2 - 左孩子:
idx * 2 + 1 - 右孩子:
idx * 2 + 2
上浮 HeapifyUp(入队)
- 新元素追加到数组末尾;
- 与父节点比较,比父小就交换,
idx更新为父索引; - 重复直到不小于父节点,或已到堆顶。
上浮只和父节点比较,完全不看兄弟节点。
下沉 HeapifyDown(出队)
- 取出堆顶元素,把数组最后一个元素移到堆顶;
- 当前节点与左右孩子比较,三者中选出最小值下标
smallest; - 若
smallest不是自己,交换并令idx = smallest继续向下; - 直到当前节点最小或到达叶子节点。
下沉会同时看左右两个孩子。
三条硬约束
- 上浮 / 下沉只做局部修复,不会全局扫描纠正堆;
- 禁止从外部直接修改底层 List——外力一改堆结构就坏了,队列没有自动纠错能力;
- 最小堆是数值越小优先级越高,业务层要自行对齐语义,不要靠传负数糊弄。
工程妥协:堆无法删除中间元素,作废任务只能等它被弹出后再过滤掉。
四、补充与易错点
PriorityQueue不是稳定队列:相同优先级的元素出队顺序不确定。需要稳定时必须把序号编进优先级((priority, seq))。- 没有
DecreaseKey/Remove:想修改已入队元素的优先级,只能重新入队再靠"出队时校验"过滤旧条目。C# 的PriorityQueue提供UnorderedItems可以枚举全部元素,但删除仍是 O(n)。 SortedList也是有序字典:底层是数组,内存更省、遍历更快,但插入删除是 O(n)(要搬移元素),只适合"读多写极少"的场景。SortedDictionary的枚举是有序的:这是它相对Dictionary的唯一优势,别为了"有序"去承担 O(log n) 的插入成本——真需要有序输出时,排序一次通常更划算。- 手写堆的容量增长:底层
List扩容时同样会搬移,最好在构造时给出预估容量。 - 自定义比较器要注意方向:最小堆配
Comparer<T>.Create((a,b) => a.Priority.CompareTo(b.Priority)),方向写反会变成最大堆,且不会报错,只表现为"顺序不对"。

