Skip to content
Katabench
Try free
9 min read The Katabench team

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:

C#
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.

What the heap promises

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.

Making ties stable

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:

C#
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++));
}
Text
a b c d e f g

Each 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.

Living without decrease-key

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:

C#
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.

Top-K with a bounded heap

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.

C#
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.

The cost of a top-K pass depends on how often the second case happens. On rising input it happens for almost every value.

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:

Text
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,000

At 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.

When a sorted array beats the heap

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

More like this: C# coding challenges →

Get new katas and .NET tips in your inbox

A short note when fresh kata land, plus the C# and performance tricks behind the grading. No spam, unsubscribe anytime.