In .NET's PriorityQueue<TElement,TPriority>, which item does Dequeue return first, what order do equal priorities come out in, and can you foreach over it?
answer
- min-heap, not max
- four children per node
- ties have no order
- UnorderedItems is literal
basics
~20 sDequeue returns the element with the lowest priority under the queue's IComparer<TPriority>. Equal priorities come out in no guaranteed order, and the class has no GetEnumerator, so foreach fails with CS1579; UnorderedItems walks the heap unsorted.
solid answer
~40 s`PriorityQueue<TElement,TPriority>`, added in .NET 6, is a 4-ary min-heap of element-priority pairs, so `Dequeue` and `Peek` return the element whose priority is smallest under `Comparer<TPriority>.Default` or the `IComparer<TPriority>` you pass. For largest-first you pass a reversing comparer such as `Comparer<int>.Create((a, b) => b.CompareTo(a))`. It is not stable: items with equal priority come out in whatever order the heap leaves them, so if ties must be first-come, first-served you add a sequence number to the priority, for example a `(int, long)` tuple. It also implements no collection interface, so `foreach` over it does not compile (CS1579); `UnorderedItems` lets you inspect the pairs in heap storage order, which is not sorted.
code
csharp · 19 linesvar jobs = new PriorityQueue<string, int>();
jobs.Enqueue("normal-A", 5);
jobs.Enqueue("rush-1", 1);
jobs.Enqueue("normal-B", 5);
jobs.Enqueue("normal-C", 5);
jobs.Enqueue("normal-D", 5);
jobs.Enqueue("rush-2", 1);
Console.WriteLine("Unordered: " + string.Join(", ", jobs.UnorderedItems.Select(x => $"{x.Element}({x.Priority})")));
Console.Write("Dequeued: ");
while (jobs.TryDequeue(out var job, out var priority)) Console.Write($"{job}({priority}) ");
Console.WriteLine();
long seq = 0;
var fifoTies = new PriorityQueue<string, (int Priority, long Seq)>();
foreach (var name in new[] { "normal-A", "normal-B", "normal-C", "normal-D" })
fifoTies.Enqueue(name, (5, seq++));
Console.Write("With sequence: ");
while (fifoTies.TryDequeue(out var j, out _)) Console.Write(j + " ");go deeper
Remember that the smallest priority value comes out first and that the priority is passed separately from the element at Enqueue time.
Explain the min-heap, the comparer that decides order, the reversing comparer for largest-first, why ties are unordered, and why foreach fails with CS1579.
Catch code that relies on insertion order among equal priorities or on UnorderedItems being sorted, and fix it with a sequence number in the priority.
When a scheduler's fairness matters, make the tie-break rule explicit in the priority type so the behaviour is specified rather than an accident of the heap.
## What PriorityQueue is `PriorityQueue<TElement,TPriority>` (in `System.Collections.Generic`, added in .NET 6) stores **pairs**: an element and a separate priority value. Internally it is an array of `(TElement Element, TPriority Priority)` tuples arranged as a **4-ary min-heap**: each node has up to four children, and every node's priority is less than or equal to its children's under the queue's comparer. The root, index 0, is always a minimum. The type's members follow from that layout: - `Enqueue(element, priority)` places the pair at the end and sifts it up: O(log n). - `Dequeue()` returns the root element and sifts the last node down: O(log n). `Peek()` reads the root: O(1). - `TryDequeue(out element, out priority)` and `TryPeek(out element, out priority)` return both halves of the pair and return `false` on an empty queue; `Dequeue()` and `Peek()` throw `InvalidOperationException` instead. - The constructor that takes `IEnumerable<(TElement, TPriority)>`, and `EnqueueRange(...)` on an empty queue, build the heap in one O(n) heapify pass. ## Lowest first, under whichever comparer you pass "Priority" is a sort key, and the queue always serves the **smallest** key first. With `PriorityQueue<string,int>`, priority 1 beats priority 5. The comparison comes from the `IComparer<TPriority>` passed to the constructor, or `Comparer<TPriority>.Default` when none is passed. For a print shop that wants the *largest* number first, either store negated priorities or pass a reversing comparer: ```csharp var maxFirst = new PriorityQueue<string, int>( Comparer<int>.Create((a, b) => b.CompareTo(a))); ``` The reversing comparer is clearer, and it avoids the edge case that `-int.MinValue` overflows. The priority type does not have to be a number. Any `TPriority` works as long as the comparer can order it: a `DateTime` deadline, an enum such as `Urgency.Rush`, or a record with a custom `IComparer<T>`. Whatever you choose, the queue never inspects the element. A `PrintJob` class with its own `Priority` property is ordered only by the value you pass as the second argument to `Enqueue`, so the two can drift apart if the job object is later edited. Passing the priority explicitly at enqueue time, from one place in the code, keeps them consistent. ## Ties come out in no promised order A heap only guarantees that the root is *a* minimum. Among equal priorities it promises nothing, and the order depends on where each pair landed during sifting. In the example, four normal jobs enqueued A, B, C, D at priority 5 came out D, C, B, A on this runtime. That is an observation, not a contract: change the number of items or the enqueue sequence and you will see a different order. When ties must be first-come, first-served, put the tie-breaker in the priority itself: 1. Keep a `long` counter that increments on every enqueue. 2. Use `(int Priority, long Sequence)` as `TPriority`. 3. `ValueTuple` compares element by element, so equal priorities fall back to the sequence number and come out in insertion order. ## You cannot foreach over it Unlike `Queue<T>`, the class implements no collection interface and has no `GetEnumerator`. `foreach (var job in jobs)` fails to compile with **CS1579** ("foreach statement cannot operate on variables of type 'PriorityQueue<string, int>' because 'PriorityQueue<string, int>' does not contain a public instance or extension definition for 'GetEnumerator'"). The escape hatch is `UnorderedItems`, an `IReadOnlyCollection<(TElement Element, TPriority Priority)>` that walks the heap array **in storage order**, which is not sorted. To list items in priority order you must dequeue them (destroying the queue), or copy `UnorderedItems` and sort the copy. | Want | Use | Order | |---|---|---| | next job | `Peek()` / `TryPeek` | the minimum | | all jobs, in priority order | repeated `TryDequeue` | ascending, ties unspecified | | inspect without removing | `UnorderedItems` | heap storage order | | FIFO among equal priorities | `(priority, sequence)` as `TPriority` | ascending, then insertion | ## What interviewers listen for - **Min-first**: the lowest value is the highest urgency unless you reverse the comparer. - **No stability**: equal priorities are not served in insertion order. - **No enumeration in order**: CS1579 on `foreach`, and `UnorderedItems` is literally unordered. - **Priority is separate from the element**: the queue never asks the element for its priority, so a job's own `Priority` property is irrelevant unless you pass it at `Enqueue` time. - **No update operation**: changing a queued job's priority is its own problem, handled by re-enqueueing or rebuilding.
- What does PriorityQueue.EnqueueDequeue return when the new item's priority equals the current minimum?It returns the new element straight back and leaves the queue unchanged. The source only replaces the root when the new priority compares strictly greater than the root's; otherwise the new item would itself be a minimum, so returning it is equivalent to enqueueing and dequeueing it, without touching the heap.
- How do you list a PriorityQueue's items in priority order without emptying it?Copy `UnorderedItems` and sort the copy, for example with LINQ's `OrderBy(x => x.Priority)`, or build a second queue from `UnorderedItems` and drain that one. `UnorderedItems` itself only walks the heap array, which is not sorted, and the queue has no ordered enumerator.
- PriorityQueue dequeues the highest priority number first.
- Items with equal priority come out in insertion order.
- foreach over a PriorityQueue lists items in dequeue order.
- UnorderedItems returns the pairs sorted by priority.
- PriorityQueue reads each element's own Priority property to order it.