学习笔记19 10 月, 2026· 约 4 分钟

优先队列与最小堆

优先队列与最小堆 一、核心结论 SortedDictionary<TKey,TValue 不能直接当优先队列用,不推荐。 .NET 6+ 官方提供 PriorityQueue<TElement,TPriority ,底层是最小堆。 二、为什么 SortedDictionary 不合适 SortedDictionary


优先队列与最小堆

一、核心结论

SortedDictionary<TKey,TValue> 不能直接当优先队列用,不推荐。 .NET 6+ 官方提供 PriorityQueue<TElement,TPriority>,底层是最小堆。

二、为什么 SortedDictionary 不合适

SortedDictionary 底层是红黑树,两个硬伤:

  1. Key 必须唯一,无法直接存放多个相同优先级的任务。补救方案是用复合键 (优先级, 自增序号)。
  2. 它要维护全集有序,而优先队列只需要保证堆顶最小,红黑树多做了一大堆无用功。

性能对比

  • 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(入队)

  1. 新元素追加到数组末尾;
  2. 与父节点比较,比父小就交换,idx 更新为父索引;
  3. 重复直到不小于父节点,或已到堆顶。

上浮只和父节点比较,完全不看兄弟节点。

下沉 HeapifyDown(出队)

  1. 取出堆顶元素,把数组最后一个元素移到堆顶;
  2. 当前节点与左右孩子比较,三者中选出最小值下标 smallest;
  3. 若 smallest 不是自己,交换并令 idx = smallest 继续向下;
  4. 直到当前节点最小或到达叶子节点。

下沉会同时看左右两个孩子。

三条硬约束

  1. 上浮 / 下沉只做局部修复,不会全局扫描纠正堆;
  2. 禁止从外部直接修改底层 List——外力一改堆结构就坏了,队列没有自动纠错能力;
  3. 最小堆是数值越小优先级越高,业务层要自行对齐语义,不要靠传负数糊弄。

工程妥协:堆无法删除中间元素,作废任务只能等它被弹出后再过滤掉。

四、补充与易错点

  • 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)),方向写反会变成最大堆,且不会报错,只表现为"顺序不对"。