优先级相同时的优先级队列行为

Question

我正在尝试 .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”之前排队。

Answer 1

永远无法保证同等优先级的元素将获得什么顺序。

但是，从源代码来看，列表的机制不仅仅是一个有序数组，并且使用来自最后一个节点的某种链接样式列表，将每个节点向后移动一步，直到它使用您提供的任何比较器找到比较（或默认），直到它找到可以去的地方。

在这种情况下，插入的顺序很重要，并且可以准确地生成您所看到的工件。

为什么你可能会问，可能是因为它更有效，但是人们需要追踪设计记录、讨论和论文试验来了解他们为什么专门选择这个。

Answer 2

你可能对堆/优先级队列有误解。

不保证一切正常。只有最上面的一个才能保证是最小值或最大值。

Answer 3

正如其他答案中提到的，不保证顺序。但是，如果您需要保证特定顺序，则可以使用元组

(weight, index)

作为优先级作为解决方法。元组中的第一项是您的体重，第二项是指数。

例如：

var priortyQueue = new PriorityQueue<string,(int,int)>();
priortyQueue.Enqueue("A", (1, 0));
priortyQueue.Enqueue("C-1",(3, 1));
priortyQueue.Enqueue("D", (4, 2));
priortyQueue.Enqueue("C-2",(3, 3));

while (priortyQueue.TryDequeue(out var str,out var priority))
{
    Console.WriteLine($"Element:{str} with Priority {priority}");
}

输出：

Element:A with Priority (1, 0)
Element:C-1 with Priority (3, 1)
Element:C-2 with Priority (3, 3)
Element:D with Priority (4, 2)