C# PriorityQueue: tie order, decrease-key and top-K
C# PriorityQueue is a quaternary heap with no stable tie order. A bounded top-K ran 100x faster than sorting on shuffled data and 7x slower on ascending.
Seven equal-priority jobs, enqueued as a through g, came out of PriorityQueue<string, int> as
a g f e d c b:
var queue = new PriorityQueue<string, int>();
foreach (var job in new[] { "a", "b", "c", "d", "e", "f", "g" })
{
queue.Enqueue(job, 1);
}The documentation says the type does not guarantee first-in-first-out order for equal priorities, and that output shows how far from FIFO it can get. The structure underneath is a heap, and nearly every surprise in this API follows from that.
The docs describe an array-backed, quaternary min-heap. Quaternary means each node has four children
instead of the two in a textbook binary heap. In the
source,
the children of node i sit at indices 4i + 1 to 4i + 4, and the parent of node j is at
(j - 1) / 4. A million elements fit in about 10 levels, since log4 of 1,000,000 is 9.97, where a binary
heap would need about 20. Each level on the way down compares more children, so a shallower tree is a
trade, not a free win.
The only ordering rule is that a parent is not greater than its children. So the minimum is always at the
root, Peek is cheap, and everything else is only partly ordered. Enumerating UnorderedItems on a queue
holding priorities 9, 3, 7, 1, 5 and 2 gave 1 2 7 3 5 9, which has the smallest first and no meaningful
order after that.
The tie behavior comes from how removal works. Dequeue takes the root, moves the last array element to
the top and sifts it down. With equal priorities it has no reason to move, so the most recently stored
element jumps straight to the front. That is why g came second.
If order among equals matters, make it part of the priority. A sequence number that only goes up gives every item a unique position, and a value tuple compares its fields in order:
var queue = new PriorityQueue<string, (int Priority, long Sequence)>();
long sequence = 0;
foreach (var job in new[] { "a", "b", "c", "d", "e", "f", "g" })
{
queue.Enqueue(job, (1, sequence++));
}a b c d e f gEach heap node grows from 16 to 24 bytes, and ties cost one more comparison. A test for this needs at least
three items. Two equal-priority items came out as a b from the plain queue, while three came out as
a c b, so a two-item test would pass against the very bug it exists to catch. Boundary thinking applies to collection sizes as
well as to numbers.
Classic graph algorithms lower the priority of an item already in the heap. This type has no such
operation, and you cannot fake it by changing a priority object in place. With a reference-type priority and a
custom comparer, changing an enqueued item's priority from 5 to 1 left Peek returning the item with priority 3,
because the heap only restores order during its own operations.
.NET 9 added Remove,
so you could remove and enqueue again. The docs say it scans every element linearly, and that with duplicates
the entry it removes is not deterministic. That is fine for an occasional cancellation and costly inside a
loop.
The usual answer is lazy deletion: enqueue the better entry, leave the old one where it is, and ignore it when it surfaces. Here it is in Dijkstra's shortest path algorithm:
var best = new Dictionary<string, int> { ["A"] = 0 };
var frontier = new PriorityQueue<string, int>();
frontier.Enqueue("A", 0);
while (frontier.TryDequeue(out var node, out var distance))
{
if (distance > best[node]) continue; // stale entry, a shorter path was found later
foreach (var (to, cost) in graph[node])
{
var candidate = distance + cost;
if (!best.TryGetValue(to, out var known) || candidate < known)
{
best[to] = candidate;
frontier.Enqueue(to, candidate);
}
}
}On a four-node test graph this produced A=0, B=2, C=1, D=3 and skipped 2 stale entries. The cost is that the
queue can hold one entry per improvement instead of one per node, so its size is bounded by the number of
edges relaxed. On dense graphs, that is worth watching. A crawler frontier has the
same shape: rescheduling a URL is easier as a new entry with a check on the way out.
Picking the k largest values from a large input is where this type earns its keep. Say you want the 1,000 slowest request durations from a day of samples. The idea looks backwards at first: use a min-heap of size k, so the root is the smallest value you are keeping and therefore the first one to evict.
public static int[] TopK(int[] values, int k)
{
ArgumentOutOfRangeException.ThrowIfNegativeOrZero(k);
var heap = new PriorityQueue<int, int>(k + 1);
foreach (var value in values)
{
if (heap.Count < k)
{
heap.Enqueue(value, value);
}
else if (value > heap.Peek())
{
heap.DequeueEnqueue(value, value);
}
}
var result = new int[heap.Count];
for (var i = result.Length - 1; i >= 0; i--)
{
result[i] = heap.Dequeue();
}
return result;
}DequeueEnqueue removes the root and adds the new element as one operation. EnqueueDequeue is a valid
alternative that folds the comparison in, though it is not in the benchmark below. Memory stays at k entries
no matter how long the input is, so this also works on a stream you could never hold in an array.
A quaternary min-heap holding the five largest values seen so far
301
index 0, smallest kept
children of i sit at 4i + 1 to 4i + 4
412
index 1
530
index 2
388
index 3
467
index 4
The children have no order among themselves. Only the root is promised.
Next value: 290
Not above the root. Discarded in one comparison.
Next value: 601
Above the root. 301 leaves and 601 sifts down, about log4(k) levels.
On paper, O(n log k) beats the O(n log n) of sorting. The table puts three approaches on 1,000,000 integers. "Sort" clones the array, sorts it and slices. "Full heap" builds a max-heap of all N through the bulk constructor and dequeues k. The setup was BenchmarkDotNet 0.15.8, Release, on .NET 10.0.9, Windows 11 and a Ryzen 9 9950X3D. That is one pass with other jobs running on the box, enough to trust a 7x gap and too little to trust a 10% one.
| Input | k | Sort | Full heap | Bounded heap | Bounded allocates |
|---|---|---|---|---|---|
| Shuffled | 10 | 58.8 ms | 9.9 ms | 0.6 ms | 224 B |
| Shuffled | 1,000 | 59.6 ms | 12.4 ms | 1.3 ms | 12 KB |
| Shuffled | 100,000 | 64.4 ms | 33.4 ms | 36.7 ms | 1.2 MB |
| Ascending | 10 | 5.5 ms | 6.7 ms | 4.5 ms | 224 B |
| Ascending | 1,000 | 7.9 ms | 9.5 ms | 34.1 ms | 12 KB |
| Ascending | 100,000 | 7.6 ms | 17.1 ms | 54.8 ms | 1.2 MB |
Sort allocated about 4 MB in every row and the full heap about 17 MB.
On shuffled data with small k, the bounded heap wins by a wide margin: about 100 times faster than sorting at k = 10. At k = 100,000 its lead over sorting shrinks to under a factor of two, and the full heap is level with it. On ascending data the result flips, and sorting is about 7 times faster at k = 100,000.
Counting the replacements explains the table. For a random order, value number i is in the top k so far with probability k/i, which sums to about k times ln(n/k). The counts from a separate instrumented run are close:
k = 10 shuffled: 145 predicted: 115 ascending: 999,990
k = 1,000 shuffled: 6,899 predicted: 6,908 ascending: 999,000
k = 100,000 shuffled: 230,380 predicted: 230,259 ascending: 900,000At k = 1,000 the bounded heap made 6,899 replacements on shuffled input and took 1.3 ms. On ascending input it made 999,000 and took 34.1 ms.
Every other value costs one comparison against the root and is thrown away. So for shuffled data at k = 10, the heap does real work about 145 times in a million values. On ascending input, every new value is the best so far, so it pays a full sift each time. Nearly sorted input is not exotic. IDs and timestamps often arrive close to ascending, and so can a metric that drifts upward during a load test.
The sort column has its own lesson. Sorting already-ascending integers took about a tenth of the time of sorting shuffled ones, so a complexity class alone would have misled you about both columns. This is the same reason to measure with real data shapes rather than trust the notation.
Use the bounded heap when k is small compared with n, when the input arrives as a stream, or when memory is the constraint. That last advantage holds in every row above, including those where it lost on time. Use a sort when k is a large fraction of n and you already hold the data, or when the input is likely to arrive nearly sorted and you can afford the copy.
One more check before you ship either: ties. A bounded heap keeps an arbitrary subset of values equal to the k-th best, and which ones depends on arrival order. If the result is shown to people or compared across runs, add a tie-break to the priority as in the stable queue above.
The top-K kata linked from this post runs on 200,000 elements under a time budget, where hidden input size decides the result, as Writing fast C# describes. The test-writing kata beside it has a different target: your operation sequences must catch planted bugs in priority and tie order. The wider set is under C# coding challenges.
Practice what you just read
- Open in the editor: Top K Frequent Elements
Algorithm Medium Free, no account needed
Top K Frequent Elements
Return the k most frequent values, most frequent first.
- Open in the editor: Test Stable Priority Ordering
Test writing Medium Free, no account needed
Test Stable Priority Ordering
Write operation sequences that distinguish priority order, FIFO ties, peeking, and queue-instance isolation.
More like this: C# coding challenges →