Priority queue in C#

Problem

Who goes first

The delivery dispatcher hands orders to the couriers. Every order has a deadline: in how many minutes it must be at the customer's door. A free courier always gets the most urgent order.

Orders come in all the time. On a Friday evening in a big city 10,000 wait at once, and 100,000 pass through in a day.

The first solution is a list sorted by deadline. For every new order you add it and sort the list again. Sorting is O(n log n) (see merge sort), and that is for every order. Even the smartest sort, which notices that the list is almost sorted, must at least walk through it: n steps for every new order.

And the courier does not need the whole order of the list. Only the first one.

The idea

A queue that only knows who is first

A structure with two actions: add an order and take the most urgent. This is a priority queue. It does not promise an order for all of them, only who is first.

That is exactly what the heap from the lesson on heap sort does. Here it is turned around: a min-heap, where every parent is at most as big as its children. Then the earliest deadline is always at index 0.

Taking you already know from heap sort. The top leaves, the last element takes its place and sinks down. The difference is that it sinks towards the more urgent child.
Adding is the new part: sift up. The new order goes to the end of the array. Then it is compared with its parent at index (i - 1) / 2. If it is more urgent, they swap places, and it keeps going up. It stops when the parent is more urgent or when it reaches the top.

See it

Sift up and sift down

Adding: to the end, then up.

public void Push(Order order)
{
    items.Add(order);
    int i = items.Count - 1;
    while (i > 0)
    {
        int parent = (i - 1) / 2;
        if (!Less(i, parent)) return;
        Swap(i, parent);
        i = parent;
    }
}

Taking: the top leaves, the last one takes its place and sinks.

public Order Poll()
{
    Order top = items[0];
    items[0] = items[^1];
    items.RemoveAt(items.Count - 1);
    if (items.Count > 0) SiftDown(0);
    return top;
}

private void SiftDown(int i)
{
    int n = items.Count;
    while (true)
    {
        int low = i;
        int left = 2 * i + 1, right = 2 * i + 2;
        if (left < n && Less(left, low)) low = left;
        if (right < n && Less(right, low)) low = right;
        if (low == i) return;
        Swap(i, low);
        i = low;
    }
}

Six orders are waiting. A new one with 18 minutes comes in, and the courier takes the most urgent:

Order[] waiting =
[
    new Order("A-101", 10),
    new Order("A-102", 15),
    new Order("A-103", 30),
    new Order("A-104", 20),
    new Order("A-105", 25),
    new Order("A-106", 40)
];
var queue = new DeadlineQueue();
foreach (Order o in waiting) queue.Push(o);
Console.WriteLine($"Heap: {queue.Deadlines()}");
queue.Push(new Order("A-107", 18));
Console.WriteLine($"After A-107: {queue.Deadlines()}");
Order next = queue.Poll();
Console.WriteLine($"The courier takes {next.Id} ({next.Deadline} min)");
Console.WriteLine($"Left: {queue.Deadlines()}");

Heap: [10, 15, 30, 20, 25, 40]
After A-107: [10, 15, 18, 20, 25, 40, 30]
The courier takes A-101 (10 min)
Left: [15, 20, 18, 30, 25, 40]

class DeadlineQueue
{
    private readonly List<Order> items = [];

    public void Push(Order order)
    {
        items.Add(order);
        int i = items.Count - 1;
        while (i > 0)
        {
            int parent = (i - 1) / 2;
            if (!Less(i, parent)) return;
            Swap(i, parent);
            i = parent;
        }
    }

    public Order Poll()
    {
        Order top = items[0];
        items[0] = items[^1];
        items.RemoveAt(items.Count - 1);
        if (items.Count > 0) SiftDown(0);
        return top;
    }

    private void SiftDown(int i)
    {
        int n = items.Count;
        while (true)
        {
            int low = i;
            int left = 2 * i + 1, right = 2 * i + 2;
            if (left < n && Less(left, low)) low = left;
            if (right < n && Less(right, low)) low = right;
            if (low == i) return;
            Swap(i, low);
            i = low;
        }
    }

    private bool Less(int i, int j) =>
        items[i].Deadline < items[j].Deadline;

    private void Swap(int i, int j) =>
        (items[i], items[j]) = (items[j], items[i]);

    public int Count => items.Count;

    public string Deadlines()
    {
        var all = items.Select(o => o.Deadline);
        return $"[{string.Join(", ", all)}]";
    }
}

Step by step, in words

Six waiting orders, deadlines in minutes. A min-heap: every parent is at most its children, so the most urgent, 10, is on top.
Push: a new order with 18 minutes goes to the end of the array, index 6. In the tree it is a child of 30.
Sift up: the parent of 6 is (6 - 1) / 2 = 2. 18 is more urgent than 30, so they swap.
The parent of 2 is 0, with 10 minutes. 10 is more urgent than 18: the order stops. One swap, at most one per level.
Poll: the courier takes the top, the order with 10 minutes. There is a hole at index 0.
The last element, 30, jumps to the top and the array shrinks to six. Now SiftDown puts it in its place.
Sift down, as in heap sort but towards the more urgent child: 30 against 15 and 18 swaps with 15, then against 20 and 25 swaps with 20.
Index 3 has no children: done. On top is 15, the next most urgent. Both moves cost O(log n): the height of the tree.

The array is not sorted: 18 comes before 20. Only what matters is sorted: the earliest deadline is on top.

Try it

Predict the output

Five orders go into an empty queue. What is in the array after that?

var queue = new DeadlineQueue();
queue.Push(new Order("B-1", 40));
queue.Push(new Order("B-2", 25));
queue.Push(new Order("B-3", 30));
queue.Push(new Order("B-4", 10));
queue.Push(new Order("B-5", 35));
Console.WriteLine(queue.Deadlines());

Answer

[40, 25, 30, 10, 35]

[10, 25, 30, 35, 40]

[10, 25, 30, 40, 35]

Try it

Fill in

Sifting up compares the element at index i with its parent. Where is the parent?

int parent = ;

The idea

What it costs

Adding: at most one comparison per level. A tree of n elements has about log₂ n levels: O(log n).
Taking: two comparisons per level while sinking: also O(log n).
Who is first: the top is at index 0, without a single comparison: O(1).

Run the dispatcher with both versions. Orders come in one by one, after every second one a courier takes the most urgent, and at the end the couriers take the rest. The count is the comparisons between two deadlines:

Sorted list: re-sort after every order O(n²)
Min-heap: sift up and sift down O(n log n)

Algorithm	n = 10	n = 1,000	n = 10,000	n = 100,000
Sorted list: re-sort after every order	11	63,430	6,250,042	≈ 625,004,200
Min-heap: sift up and sift down	28	17,397	256,807	3,386,161

The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.

class DeadlineQueue
{
    private readonly List<Order> items = [];

    public void Push(Order order)
    {
        items.Add(order);
        int i = items.Count - 1;
        while (i > 0)
        {
            int parent = (i - 1) / 2;
            if (!Less(i, parent)) return;
            Swap(i, parent);
            i = parent;
        }
    }

    public Order Poll()
    {
        Order top = items[0];
        items[0] = items[^1];
        items.RemoveAt(items.Count - 1);
        if (items.Count > 0) SiftDown(0);
        return top;
    }

    private void SiftDown(int i)
    {
        int n = items.Count;
        while (true)
        {
            int low = i;
            int left = 2 * i + 1, right = 2 * i + 2;
            if (left < n && Less(left, low)) low = left;
            if (right < n && Less(right, low)) low = right;
            if (low == i) return;
            Swap(i, low);
            i = low;
        }
    }

    private bool Less(int i, int j) =>
        items[i].Deadline < items[j].Deadline;

    private void Swap(int i, int j) =>
        (items[i], items[j]) = (items[j], items[i]);

    public int Count => items.Count;

    public string Deadlines()
    {
        var all = items.Select(o => o.Deadline);
        return $"[{string.Join(", ", all)}]";
    }
}

With 10 orders the sorted list makes 11 comparisons and the heap 28: with few orders the list is perfectly fine. With 10,000 it is 6,250,042 against 256,807. With 100,000 the heap makes 3,386,161, and the list about 625 million. Bench does not run that one; it estimates it from the curve.

The sorted list in Bench is at its best: the new order only slides to its place, and nothing else is sorted. It is still O(n) per order, because it passes on average half the list. The heap is O(log n) per order.

More precisely, if you are curious

Which sort notices that the list is almost sorted? TimSort, used by sort in Python, List.sort and Collections.sort in Java and Array.prototype.sort in JavaScript (see the built-in sort). It finds the sorted part with about n comparisons and puts the new element into it: O(n) per order. Bench counts an even cheaper version, sliding from the end, and it still comes out O(n). C# List.Sort is introsort and does not look for sorted parts: for every order it makes about n log n comparisons, even more.

Why is sifting up fast in practice too? A new order is usually somewhere in the middle by urgency. Half the elements of a heap are leaves, a quarter are just above them, and so on. So on average a random order stops after a level or two. The worst case (the new one is the most urgent of all) is still only log₂ n.

Try it

Find the bug

A colleague wrote the sinking, but the couriers sometimes leave with a later order before an earlier one:

private void SiftDown(int i)
{
    int n = items.Count;
    while (true)
    {
        int low = i;
        int left = 2 * i + 1, right = 2 * i + 2;
        if (left < n && Less(left, low)) low = left;
        if (right < n && Less(right, i)) low = right;
        if (low == i) return;
        Swap(i, low);
        i = low;
    }
}

var queue = new DeadlineQueue();
queue.Push(new Order("C-1", 5));
queue.Push(new Order("C-2", 10));
queue.Push(new Order("C-3", 20));
queue.Push(new Order("C-4", 30));
queue.Push(new Order("C-5", 40));
queue.Push(new Order("C-6", 50));
var taken = new List<int>();
while (queue.Count > 0) taken.Add(queue.Poll().Deadline);
Console.WriteLine($"[{string.Join(", ", taken)}]");

[5, 20, 10, 30, 40, 50]

Which line has the bug?

Pick the line with the bug.

See it

The ready-made queues of every language

In a project you do not write a heap yourself. Almost every language has a priority queue, and each one has its quirk.

PriorityQueue<TElement, TPriority> has been in C# since .NET 6. The element and the priority are separate: Enqueue("A-101", 30). The queue is a min-heap by priority: Dequeue takes the smallest, Peek shows it.

The quirks: UnorderedItems is not in order. And inside, the heap is not binary but has up to four children per node: that is why the order differs from the one in our queue. Fewer levels mean less moving around in memory.

var queue = new PriorityQueue<string, int>();
queue.Enqueue("A-101", 30);
queue.Enqueue("A-102", 10);
queue.Enqueue("A-103", 20);
queue.Enqueue("A-104", 25);
Console.WriteLine($"Most urgent: {queue.Peek()}");
Console.Write("Inside:");
foreach (var (_, deadline) in queue.UnorderedItems)
    Console.Write($" {deadline}");
Console.WriteLine();
while (queue.TryDequeue(out string? orderId, out int deadline))
{
    Console.WriteLine($"{orderId} ({deadline} min)");
}

Most urgent: A-102
Inside: 10 30 20 25
A-102 (10 min)
A-103 (20 min)
A-104 (25 min)
A-101 (30 min)

More precisely, if you are curious

None of these queues is stable: two orders with the same deadline can come out in any order (see stability). If the order of arrival matters, add a sequence number, as in Python above.

None of the three can change the deadline of an order that is already waiting. remove in Java searches for the element linearly: O(n). The usual solution is to add the order again with the new deadline and skip the old copy when it comes out. Dijkstra works like that too, in the upcoming graphs module (algo-graphs).

How it is in the other languages: Java has PriorityQueue, C# PriorityQueue<TElement, TPriority> (since .NET 6), Python heapq (functions on a list), and JavaScript has no built-in priority queue.

See it

Two more jobs for a heap

The top k. Which 10 out of a million products sell the most? A min-heap that never holds more than 10 elements: every new one is compared with the top. That is in the lesson on the heap, with a Bench too.

Merging k sorted lists. Three warehouses send their orders sorted by deadline. You need one shared route, again by deadline. The heap holds only the head of every list. You take the earliest one, and in its place you put the next one from the same warehouse:

int[][] lists = [[5, 20, 45], [10, 15, 50], [12, 30]];
string[] names = ["North", "South", "Centre"];
var heads = new PriorityQueue<(int List, int Index), int>();
for (int k = 0; k < lists.Length; k++)
{
    heads.Enqueue((k, 0), lists[k][0]);
}
var route = new List<string>();
while (heads.TryDequeue(out var h, out int deadline))
{
    route.Add($"{deadline} {names[h.List]}");
    int next = h.Index + 1;
    if (next < lists[h.List].Length)
    {
        heads.Enqueue((h.List, next), lists[h.List][next]);
    }
}
Console.WriteLine($"Route: {string.Join(", ", route)}");

Route: 5 North, 10 South, 12 Centre, 15 South, 20 North, 30 Centre, 45 North, 50 South

The heap never holds more than k elements (3 here). So N orders cost O(N log k), not O(N log N) for sorting everything. This is also how the sorted parts of a file that does not fit in memory are merged.

More precisely, if you are curious

Python has a ready-made merge: heapq.merge. In Java, C# and JavaScript you write it as here.

Merge sort merges sorted parts too, but two at a time (merge sort). A heap merges k at once.

Exercise

A fair queue

Solve the task in your editor.

Same deadline, the earlier one first. Make a queue FairQueue in which, with equal deadlines, the order that came in earlier goes out first. Keep a sequence number with every order and compare by deadline first, then by number. Run it with the orders A-1 (30), A-2 (20), A-3 (30), A-4 (20), A-5 (10), A-6 (20), in this order:

Order: A-5, A-2, A-4, A-6, A-1, A-3

More tasks

Max-heap. Flip the comparison and make a queue that gives the most expensive order first.
Count the comparisons. Add a counter to sift up and sift down and run 1000 random orders. How many comparisons fall on one order?
The top three. How do you get the three most urgent orders without taking the others out of the queue?

Test

Check yourself

1. What does a priority queue promise?It keeps the elements sorted so you can walk them in orderIt takes out the most urgent element and accepts new ones, without sorting everythingIt takes the elements out in the order they came in

2. A new order goes into a heap of 1,000,000 orders. At most how many comparisons does sifting up make?About 1000About 20About 1,000,000

3. In Python you keep orders as (deadline, dict) in heapq. Two orders have the same deadline. What happens?TypeError: the tuples are compared by their second element, and dicts cannot be comparedheapq merges them into oneThe one that came in first is taken

4. Three warehouses send lists sorted by deadline, N orders in total. How do you merge them into one route?Join them into one list and sort itTake one from each warehouse in turnA heap with the head of every list: take the earliest and put in the next one from the same warehouse

Priority queue

Cookies