Introduction

When a priority queue returns items in an order you did not expect, the first reaction is often this must be a bug. In .NET, most reports about PriorityQueue turn out to be misunderstandings about heap behavior rather than a defect in the implementation.

The key detail is that PriorityQueue<TElement, TPriority> is a heap-backed queue, not a fully sorted list. It guarantees that Dequeue returns an element with the best priority according to the comparer, but it does not guarantee stable ordering for ties or sorted enumeration of the internal storage.

What .NET PriorityQueue Actually Guarantees

The built-in queue is a min-priority queue by default. Smaller priority values come out first:

1using System;
2using System.Collections.Generic;
3
4var pq = new PriorityQueue<string, int>();
5pq.Enqueue("low", 5);
6pq.Enqueue("urgent", 1);
7pq.Enqueue("normal", 3);
8
9while (pq.Count > 0)
10{
11    Console.WriteLine(pq.Dequeue());
12}

The output is:

urgent
normal
low

That part is straightforward. Confusion usually starts in one of three places: equal priorities, enumeration, or mutable priorities.

Equal Priorities Are Not Stable

A heap preserves the priority rule, not original insertion order among equal-priority items. This means two elements with the same priority may come out in either order:

1var pq = new PriorityQueue<string, int>();
2pq.Enqueue("first", 10);
3pq.Enqueue("second", 10);
4pq.Enqueue("third", 10);
5
6while (pq.Count > 0)
7{
8    Console.WriteLine(pq.Dequeue());
9}

You should not build logic that depends on equal-priority items being dequeued in insertion order unless you encode that order yourself.

A common workaround is to store a secondary tie-breaker:

1using System;
2using System.Collections.Generic;
3
4var sequence = 0L;
5var comparer = Comparer<(int Priority, long Sequence)>.Default;
6var pq = new PriorityQueue<string, (int Priority, long Sequence)>(comparer);
7
8pq.Enqueue("first", (10, sequence++));
9pq.Enqueue("second", (10, sequence++));
10pq.Enqueue("third", (10, sequence++));
11
12while (pq.Count > 0)
13{
14    Console.WriteLine(pq.Dequeue());
15}

Now the queue is effectively stable because the (priority, sequence) pair defines a strict total order.

Enumeration Is Not Sorted Output

Another frequent misunderstanding is iterating the queue and expecting fully sorted results. A heap only guarantees that the root is the next element to dequeue. The rest of the internal array is only partially ordered.

So this is not a safe way to inspect sorted priority order:

1foreach (var item in pq.UnorderedItems)
2{
3    Console.WriteLine(item);
4}

The name UnorderedItems is intentional. If you want sorted removal order, repeatedly call Dequeue or copy the data into another structure and sort explicitly.

Mutable Priorities Do Not Reheapify Themselves

If your priority value depends on mutable external state, the queue does not track those changes automatically. It only knows the priority that was supplied at enqueue time.

For example, if you enqueue a task object and then later change a property that your application conceptually treats as its priority, the queue does not reshuffle itself. To change priority, remove and reinsert, or enqueue a new entry and ignore stale ones later.

That pattern is common in graph algorithms and schedulers:

pq.Enqueue(nodeId, newDistance);

If a better distance is found later, many implementations simply enqueue the node again with the better priority and discard outdated entries when they are popped.

Diagnosing Real Bugs Versus Wrong Assumptions

Before concluding there is a Microsoft bug, verify these questions:

• Are you assuming max-heap behavior even though the built-in type is min-heap by default?
• Are you relying on stable order for equal priorities?
• Are you inspecting UnorderedItems instead of dequeue order?
• Are you changing priorities after insertion without reinserting?

If the answer to any of those is yes, the unexpected behavior is probably in the calling code, not the library.

When You Actually Need Different Semantics

If you need a max-priority queue, pass a reversed comparer for the priority type. If you need stability, include a sequence number. If you need key updates, build that explicitly on top of the queue rather than expecting a decrease-key API that does not exist.

The important design lesson is that a priority queue is a specialized performance-oriented structure. It gives you fast enqueue and dequeue for best-priority items, but it does not behave like a sorted dictionary or ordered list.

Common Pitfalls

The most common mistake is expecting equal priorities to preserve insertion order. That is not part of the contract.

Another common pitfall is printing the internal items and interpreting the output as wrong priority behavior. A heap is not fully sorted internally, so UnorderedItems can look surprising even when the queue is working correctly.

People also forget the min-heap default and assume the largest priority should come out first. If you want that behavior, you need a reversed comparer.

Finally, mutable priority data is dangerous. Once an element is inside the queue, changing external state does not update its place in the heap.

Summary

• '.NET PriorityQueue<TElement, TPriority> is a heap, not a fully sorted container.'
• 'Dequeue respects priority order, but equal-priority items are not guaranteed to be stable.'
• 'UnorderedItems is not sorted output and should not be treated like one.'
• Changing an element's conceptual priority after enqueue does not reheapify the queue.
• Most suspected PriorityQueue bugs are actually incorrect assumptions about heap semantics.