c# - 优先级相同时的优先级队列行为
问题描述
我在 .Net 6 中尝试了 PriorityQueue 并且对以下行为感到困惑。我想知道是否有人可以帮助我更好地理解它。
考虑以下代码。
var priortyQueue = new PriorityQueue<string,int>();
priortyQueue.Enqueue("A",1);
priortyQueue.Enqueue("C-1",3);
priortyQueue.Enqueue("C-2",3);
priortyQueue.Enqueue("D", 4);
while (priortyQueue.TryDequeue(out var str,out var priority))
{
Console.WriteLine($"Element:{str} with Priority {priority}");
}
这将产生如下输出。
Element:A with Priority 1
Element:C-1 with Priority 3
Element:C-2 with Priority 3
Element:D with Priority 4
这看起来不错,但请注意“C-1”和“C-2”出列的位置或顺序。
现在,如果我要更改上面的代码并在插入“C1”和“C2”之间添加另一个入队语句,情况会发生轻微变化。
var priortyQueue = new PriorityQueue<string,int>();
priortyQueue.Enqueue("A",1);
priortyQueue.Enqueue("C-1",3);
priortyQueue.Enqueue("B", 2); // change here
priortyQueue.Enqueue("C-2",3);
priortyQueue.Enqueue("D", 4);
上面的输出将是
Element:A with Priority 1
Element:B with Priority 2
Element:C-2 with Priority 3 // Order is reversed
Element:C-1 with Priority 3
Element:D with Priority 4
如您所见,“C2”和“C1”的位置现在发生了变化。我很好奇为什么优先级相同时不遵循FIFO。请注意,此行为仅适用于
- “B”的优先级低于“C1”和“C2”
- “B”排在“C1”之后和“C2”之前。
解决方案
从来没有保证同等优先级的元素将获得什么顺序。
但是,从源代码来看,列表的机制不仅仅是一个有序数组,它使用最后一个节点的某种链接样式列表,将每个节点向后移动一步,直到它使用你给它的任何比较器找到一个比较(或默认),直到它找到可以去的地方。
在这种情况下,插入的顺序很重要,并且可以准确地产生您看到的工件。
为什么您可能会问,可能是因为它更有效,但是您需要跟踪设计记录、讨论和纸质试验,以了解他们为什么特别选择它。
推荐阅读
- sql - HANA 中具有 HIERARCHY 功能的 BOM 爆炸
- r - 如何删除r中列中的特定字符?
- reactjs - 是否可以从史诗中的重新选择中获取选择器?
- flutter - 将数据添加到另一个页面上的列表 Flutter
- apache-flink - Flink 检查点与 kafka 分区有关吗?
- spring - 休眠 | 使用枚举属性转换器映射数据类型“字节”不起作用 - 错误:没有 JDBC 类型的方言映射:277630005
- c# - 将 JsonResponse 反序列化为 C# 对象
- c - C程序在我停止后给出结果
- windows - Win CMD 中的二进制文件编辑
- javascript - 使用 Xpath 唯一标识自动完成列表中具有相似文本的元素