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

Question

我正在.Net 6中试用.Net，并对下面的行为感到困惑。我想知道是否有人能帮我更好地理解它。

请考虑以下代码。

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

这看起来很好，但请注意“C1”和“C2”的排队位置或顺序。

现在，如果我要更改上面的代码，并在插入"C1“和"C2”之间添加另一个enqueue语句，则情况略有变化。

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

您可能对堆/优先级队列产生了误解。

它不一定会井然有序。只有最上面的一个保证是最小的或最大的。