.NET 6 PriorityQueue相同优先级元素出队顺序变化问题咨询

核心结论 #

.NET 官方从设计之初就明确说明：PriorityQueue 不保证同优先级元素的出队顺序符合FIFO，同优先级元素的相对顺序完全由底层堆结构的调整逻辑决定，不属于Bug，是刻意设计的性能优先特性。

底层实现逻辑 #

PriorityQueue 底层基于二叉最小堆实现，存储结构为普通数组：

• 堆的规则仅保证父节点的优先级小于等于所有子节点的优先级，不会额外存储同优先级元素的入队顺序元数据
• 元素入队时执行上浮调整，出队时执行下沉调整，调整过程中如果两个节点优先级相等，不会触发位置交换，最终的相对位置完全由插入序列、中间其他优先级元素的增删操作动态决定

两种测试场景的具体成因 #

无插入B的场景（顺序符合预期） #

连续插入同优先级的C-1、C-2时，两次插入都没有触发同优先级节点的位置调整，两者在堆数组中的位置刚好和入队顺序一致，所以出队时看起来符合FIFO，属于巧合，不代表通用规则。

插入B的场景（顺序反转） #

整个过程的堆调整步骤如下：

1. 插入A（优先级1），堆顶为A
2. 插入C-1（优先级3），作为A的子节点存入数组下标1的位置
3. 插入B（优先级2）：
   • 先放到数组末尾下标2的位置
   • 上浮调整时发现父节点A优先级1小于2，本不需要再上浮，但此时C-1的优先级3大于B的2，触发位置交换，C-1被移动到下标2的位置，B移动到下标1的位置
4. 插入C-2（优先级3）：
   • 放到数组末尾下标3的位置
   • 上浮调整时父节点是下标1的B（优先级2<3，不需要上浮），最终C-2在堆中的位置比C-1更靠近堆顶
5. 依次出队A、B之后，堆重新调整时，位置更靠前的C-2会被先选出，因此出现顺序反转

解决方案：保证同优先级FIFO #

如果需要同优先级元素严格按照入队顺序出队，可以自己增加入队序号作为次优先级：

// 次优先级用自增序号，保证同优先级先入先出
var priorityQueue = new PriorityQueue<string, (int Priority, long Sequence)>();
long sequence = 0;

priorityQueue.Enqueue("A", (1, sequence++));
priorityQueue.Enqueue("C-1", (3, sequence++));
priorityQueue.Enqueue("B", (2, sequence++));
priorityQueue.Enqueue("C-2", (3, sequence++));
priorityQueue.Enqueue("D", (4, sequence++));

ValueTuple的默认比较器会先比较第一个优先级字段，相等时自动比较第二个序号字段，序号递增即可保证同优先级先入队的元素先出队。

内容的提问来源于stack exchange，提问作者Anu Viswan