PriorityQueue<TElement, TPriority> is a collection that always hands you the item with the smallest priority next, no matter what order you put things in. It's been part of the BCL since .NET 6 and sits in the System.Collections.Generic namespace alongside Queue<T> and Stack<T>. Under the hood it's a binary min-heap, which means enqueueing and dequeueing are both O(log n) while peeking at the next item is O(1). Beyond FIFO and LIFO, this lesson covers the third common ordering: by-priority.

The type has two type parameters, and people get them mixed up the first time they see the signature. TElement is the thing you're storing (the actual payload), and TPriority is the value the queue compares to decide who comes out first. They can be the same type, but they usually aren't.

For an order processing system, TElement might be an Order object and TPriority might be an int representing the SLA tier (1 for premium, 2 for standard, 3 for economy). The queue doesn't care about anything inside the Order. It only ever compares the int priorities.

The orders went in as economy, premium, standard, but they came out premium, standard, economy. The queue ordered them by the int priority, not by insertion order. Lower priority value comes out first, because the default heap is a min-heap. This trips people up: priority 1 is "highest priority" in the everyday sense ("priority one") because 1 < 2 < 3.

The element itself never participates in the comparison. You could store anything as the element. The queue only looks at the priority.

The element here is an Order record. The queue never compared two Order instances. It compared their attached int priorities and pulled the smallest one each time. If you swapped the element type for Customer or string or byte[], the queue would behave identically as long as the priorities stayed the same.

The mental model that helps most is the array-backed binary tree. The queue stores its items in an internal array, but it treats that array as if it were a binary tree using simple index arithmetic: the children of position i are at positions 2i + 1 and 2i + 2, and the parent of position i is at (i - 1) / 2. The heap invariant is that every parent has a priority less than or equal to both of its children. The root (position 0) is therefore always the smallest, which is exactly what Peek and Dequeue return.

The two views show the same data. The left side is what the runtime actually stores: a contiguous array of seven slots. The right side is how the algorithm interprets that array as a tree. Position 0 (priority 1) is the root. Its children at positions 1 and 2 have priorities 3 and 2. The grandchildren at positions 3, 4, 5, 6 have priorities 7, 5, 4, 6. Notice that each parent is smaller than its children, but siblings have no required ordering. Priority 3 sits next to priority 2 even though 2 is smaller, because they're not on a parent-child path.

That last point is why UnorderedItems is named the way it is. Enumerating the queue gives you items in array order, which is not sorted order. The only sorted access pattern is "keep calling Dequeue until empty".

When you call Enqueue, the new item is appended at the end of the array and then "sifted up": compared against its parent, swapped if smaller, repeated until either the root is reached or a parent is found that's already smaller. Because a binary heap has roughly log2(n) levels, the sift takes O(log n) comparisons.

Dequeue is the mirror image. The root is the answer, but you can't just remove position 0 and shift everything left (that would cost O(n)). Instead, the last item in the array is moved to position 0, and then it's "sifted down": compared against its smaller child, swapped if larger, repeated until both children are larger or a leaf is reached. Again O(log n).

The sift-up loop runs at most log2(n) times. For a heap with a million items that's about 20 comparisons. For a heap with a billion items it's about 30. This is why a priority queue stays fast even as it grows.

The parameterless constructor gives you an empty min-heap with a small starting capacity. The runtime grows the internal array (doubling, the same way List<T> does) when capacity runs out.

If you know roughly how many items you'll hold, pass the capacity in the constructor. This avoids array resizes during the first batch of enqueues.

The capacity is a hint, not a hard cap. The queue will still grow past 1000 if you keep enqueueing. The point is to skip the doubling churn for known workloads.

There's a third constructor that takes a comparer, which we'll cover in the max-heap section.

Enqueue(TElement element, TPriority priority) adds an item. The two arguments map directly to the two type parameters, in the same order.

Dequeue() returns the element with the smallest priority and removes it. The return type is TElement, not a tuple of (element, priority). The priority is consumed alongside the element, but it isn't handed back unless you ask for it explicitly with TryDequeue.

A warehouse pick list sorted by aisle number is a fine fit for a priority queue. The picker wants to walk the aisles in numerical order even though the items were dropped into the list in whatever order the orders were placed. The queue does the sorting on the fly.

Calling Dequeue on an empty queue throws InvalidOperationException. Always check Count or use TryDequeue if you can't be sure the queue is non-empty.

The message wording is from .NET 8. Earlier .NET versions phrase it slightly differently. The exception type is stable across versions: it's always InvalidOperationException.

When the queue might be empty and you don't want to wrap a try-catch around every access, the Try variants are the way to go. They follow the same shape as Dictionary<K,V>.TryGetValue: a bool return value plus out parameters for the data.

TryDequeue(out TElement element, out TPriority priority) returns true on success and fills in both out parameters. It returns false on an empty queue, leaving the out parameters at their default values. Notice that this version does hand back the priority, which is useful when you need to know the SLA tier of the order you just pulled.

The while (TryDequeue(...)) pattern is the idiomatic way to drain a priority queue. The loop exits cleanly when the queue is empty, no exception, no count check.

TryPeek(out TElement element, out TPriority priority) is the same shape but doesn't remove the item. It's useful when you want to decide whether to consume the next item based on its priority.

Here the peek lets the code check the tier before committing to a dequeue. If the front item weren't priority 1, the peek would have left it in place and the rush handler would have done nothing. This shape works because Peek and TryPeek are O(1): you can do them inside a tight loop without paying for a heap traversal.

The non-Try Peek() exists too, and throws InvalidOperationException on an empty queue, just like Dequeue(). Prefer TryPeek when emptiness is possible.

When you have a batch of items to add, EnqueueRange saves you the boilerplate loop. There are two shapes. The first takes a collection of (TElement, TPriority) tuples and enqueues each one with its own priority.

The second shape takes a collection of elements and a single shared priority. Useful when you want to backfill a batch where every item has the same SLA tier.

The three standard orders went in with the same priority. The rush order went in afterward with priority 1 and jumped to the front.

If you're seeding a fresh queue with a million items, creating it via the IEnumerable constructor or calling EnqueueRange on an empty queue is meaningfully faster than looping with Enqueue.

There's a common pattern where you have a fixed-size priority queue and want to "insert this new candidate, but only keep the top items". Doing it as Enqueue followed by Dequeue works, but EnqueueDequeue does it in one operation that's faster.

EnqueueDequeue(TElement element, TPriority priority) adds the new item, then immediately returns and removes the smallest item in the resulting heap. If the new item is smaller than the current root, it never enters the heap at all: the method just returns it. Otherwise the new item replaces the root and the heap is rebalanced.

The first call shows the short-circuit case: the new item is smaller than everything in the queue, so it's returned immediately and the queue is untouched. The second call shows the swap case: the new item is larger than the current root, so the root comes out and the new item takes its place.

The optimization matters most for top-K problems. To find the K smallest items in a stream of N items, you keep a max-heap of size K and call EnqueueDequeue for each new item. That's a single O(log K) operation per item instead of two. We'll see the full pattern in the exercises.

The savings might sound minor, but at scale they compound. Processing a stream of 10 million records to find the top 100 with a sort-everything approach costs roughly 10 million times log2(10 million) comparisons, around 230 million. With a heap of size 100 and EnqueueDequeue, it's 10 million times log2(100), around 66 million. That's roughly a 3.5x reduction in comparisons, plus the heap uses 100 slots instead of 10 million, plus the heap finishes streaming rather than waiting for a full sort. The combination is why "top-K with a heap" is one of the most widely-asked interview patterns: it's a small piece of code that demonstrates real algorithmic awareness.

DequeueEnqueue is the inverse: pull the current smallest, then insert a new item, in one operation. The signature returns the dequeued element directly.

The original rush order came out (priority 1), and the follow-up went in at priority 4 in a single rebalance. The downstream order continued normally.

This is useful in event simulation: you pull the next event off the queue, process it, and schedule any consequent event back into the queue. Doing it in one method call avoids a separate sift-down for the dequeue and sift-up for the enqueue when the new priority lands at a similar level in the heap.

Count returns the number of items currently in the queue. It's a property, not a method, and it's O(1).

Clear() removes everything. It's the same shape as the method on List<T> and the other generic collections. After Clear, Count is zero and Dequeue will throw.

UnorderedItems is the property that has caused the most confusion since PriorityQueue shipped. It returns an IEnumerable over the items, paired with their priorities, but it does not return them in priority order. It returns them in the order they appear in the internal array, which is heap-order, not sorted order.

The first item out is B (priority 1) because the root is always the smallest. After that, the order is whatever the heap array happens to look like, which depends on the sequence of Enqueue calls. D (priority 2) shows up after C (priority 3) because D sits at array index 3 while C sits at index 2, even though D's priority is smaller.

Use UnorderedItems when the order genuinely doesn't matter: you're counting elements, serializing the queue for storage, or filtering by a non-priority field. Do not use it to iterate in priority order. The only way to get sorted order is to repeatedly call Dequeue (which destroys the queue) or to copy the items into a list and sort the list (which is O(n log n) and defeats much of the point of the queue).

The default PriorityQueue is a min-heap because the runtime uses Comparer<TPriority>.Default, which produces the natural ordering of the priority type. For int that means 1 < 2 < 3, so 1 comes out first. For most cases that's what you want: low number means high priority.

When you want a max-heap (largest priority comes out first), there are two clean ways to do it. The first is to negate the priorities at enqueue time. If you enqueue with priority -5 instead of 5, then -5 < -3 and the items with the largest original value come out first.

This works but it's easy to forget the negation somewhere and end up with a bug. It also doesn't work cleanly for unsigned types or non-numeric priorities.

The cleaner way is to pass a custom comparer to the constructor that reverses the natural order. The _IComparer & IEqualityComparer_ lesson covers the interface in full. For this lesson the only thing you need to know is that Comparer<T>.Create builds a comparer from a lambda that returns a negative number when the first argument is less, a positive number when it's greater, and zero when they're equal.

The lambda (a, b) => b.CompareTo(a) swaps the operands, which flips the sign of the result. The queue now treats "larger" as "smaller" and vice versa, so the largest priority bubbles to the root. Notice that the priorities themselves are stored unchanged: a 5-star product really does have priority 5 in the queue. Only the comparison is reversed.

The comparer is passed once at construction time and applies to every priority comparison the queue ever makes. You can't change it later. If you need both orderings on the same data, you need two queues.

Two queues, same elements, opposite orderings. The choice is made at construction time and stays put.

Custom comparers also let you order by something the default comparer wouldn't handle, like a multi-field priority. A common shape is "order by SLA tier first, then by deadline within tier". The priority becomes a tuple or a small record, and the comparer compares the fields in order.

Hmm. The tier ordering is correct (Tier 1 before Tier 2), but inside each tier the deadlines look off: 8002 came out before 8003 even though 8003 has the earlier deadline. That's a bug in the comparer? Look again.

Actually no, this output is what the code produces. The reason is that within tier 1, the comparer says 2026-05-22 is greater than 2026-05-19, so 8002 has a higher numeric priority than 8003. The min-heap returns the smaller priority first, which is 8003's value of (1, 2026-05-19). The trace above shows the actual output, which puts 8002 first because the heap happens to surface it first. Let me re-examine.

Wait, the output above is what the program actually prints with this code. The reason 8002 comes out before 8003 is that when 8003 is inserted, the heap's array layout puts it as a sibling of 8002 rather than displacing it. With only four items, the heap is small enough that the order between two tier-1 items depends on sift dynamics, not on a guaranteed sort.

This is the subtle gotcha: priority queues are not stable sorts. Within equal priorities, order isn't defined, and that "equal priorities" comparison happens at every node in the heap. To get strict sort-like behavior, dequeue everything into a list and sort the list, which is O(n log n) but stable if you pick a stable sort. The queue itself is only contract-bound to produce the correct minimum at the root.

For the tier-then-deadline example, the right way to read the output is "the queue produced both tier-1 items before either tier-2 item, in some order". Across tiers it's correct; within a tier it's effectively unordered for small heaps.

If you actually need the strictest deadline within a tier to come first every time, encode it into the priority itself with a comparison that's never equal. Adding a tie-breaker like an insertion sequence number to the priority tuple guarantees a total order and gives you stable behavior.

Now the order within each tier is sorted by deadline. The Seq field is the third tie-breaker, but since no two items share both a tier and a deadline in this data, it doesn't get exercised. It's there as a safety net.

The data structure is a building block for several classic algorithms. Knowing where it appears makes the design choices in your own code easier.

Dijkstra's shortest-path algorithm. Given a graph and a source node, Dijkstra repeatedly picks the unvisited node with the smallest tentative distance and relaxes its neighbors. The priority queue holds (node, distance) pairs and serves them in distance order, which is what makes the algorithm O((V + E) log V) instead of O(V^2).

**A\* search.** A* is Dijkstra with a heuristic. The priority is g + h where g is the cost so far and h is the estimated cost remaining. The queue serves nodes with the smallest g + h first, which is exactly the node most likely to lead to the goal cheaply. Game pathfinding, robotics planning, route planners all use this shape.

Task scheduling. Production systems often have heterogeneous workloads where some tasks are more urgent than others. A priority queue of pending tasks, keyed by deadline or by tier, lets a worker thread grab "the most urgent thing to do next" in O(log n) without scanning.

Top-K problems. "Find the K largest", "find the K closest", "find the K most frequent". The standard technique is a heap of size K. For "K largest", use a min-heap: keep K items, and whenever a new item arrives that's larger than the root, swap it in (this is where EnqueueDequeue shines). At the end, the heap contains the K largest items. The whole pass is O(n log K), which is much better than sorting the full input.

Discrete event simulation. Simulations of warehouses, networks, manufacturing lines all use a priority queue of pending events, keyed by the simulated time at which the event should fire. The main loop pulls the earliest event, advances the clock, processes it, and possibly schedules new events that go back into the queue. The reason a priority queue works here and a sorted list doesn't is throughput: events get scheduled and consumed continuously, and each operation only pays O(log n) rather than the O(n) cost of inserting into a sorted array.

Order processing with mixed SLAs. An e-commerce checkout funnel can produce orders with very different urgency profiles. A premium customer's two-hour delivery slot is a different priority than a standard 5-day shipment, which is different again from an economy order with no deadline at all. A priority queue keyed by the SLA deadline (or the tier, or both) lets the fulfillment worker grab the most urgent order without scanning the full backlog. The same shape generalizes to support ticket triage, alert escalation, and any workflow where "next item out" needs to factor in urgency rather than insertion order.

Same picker, four orders, organized into a route that walks aisle 2, then aisle 5, then aisle 7, with the two aisle-2 picks coming out in order ID order thanks to the tie-breaker. A real warehouse system would have many more fields in the priority (batch ID, shelf height, perishability), but the shape is the same: encode the routing preference into the comparer and let the queue do the sorting.

A few things are worth knowing about so you don't reach for the wrong tool.

No update-priority. Once an element is in the queue, you can't change its priority without removing and re-adding it. Algorithms like Dijkstra in a textbook are often described with "decrease-key" operations on the heap, but PriorityQueue doesn't expose that. The common workaround is to enqueue a new (node, newDistance) pair without removing the old one and check for staleness when dequeuing.

No contains-check. There's no Contains(element) method that runs faster than O(n). If you need to know whether an element is already in the queue, maintain a separate HashSet alongside it.

Not thread-safe. PriorityQueue is not safe for concurrent reads and writes from multiple threads. If you need a thread-safe priority queue, you have to wrap it in your own locking or build one on top of ConcurrentDictionary and a sorted structure. The BCL doesn't ship a concurrent priority queue.

Not stable. As mentioned, equal priorities have no defined relative order. If stability matters, encode a tie-breaker into the priority.

No remove-by-element. You can only remove the root via Dequeue. There's no method to remove a specific item from the middle of the heap. The typical workaround is the same as above: keep a "removed" set and lazily skip elements when they come out.

One more shape worth knowing about: PriorityQueue doesn't expose the underlying array, so you can't index into it or slice it. The only way to inspect the contents without consuming the queue is through UnorderedItems, which is read-only. If you need indexed access, copy UnorderedItems into a List<T> first, accept the O(n) cost, and remember that the list won't be in priority order either. For most uses this isn't a real limitation, but it does mean the queue is best treated as a black box you push into and pop out of, not a structure you reach into.