Priority queues

Six jobs arrive and are served, the most urgent first each time. Watch where the work goes, then switch the storage.

⋯17void pq_insert(struct pq *q, struct job j)18{19    q->items[q->size] = j;20    q->size++;21}22 23struct job pq_remove(struct pq *q)24{25    int best = 0;26    for (int i = 1; i < q->size; i++) {27        remove_work++;28        if (q->items[i].priority < q->items[best].priority)29            best = i;30    }31    struct job j = q->items[best];32    q->size--;33    q->items[best] = q->items[q->size];34    return j;35}36 37int main(void)38{39    struct pq q = { .size = 0 };40    const struct job jobs[6] = { { 4, 1 }, { 9, 2 }, { 2, 3 }, { 7, 4 }, { 1, 5 }, { 5, 6 } };41    const char plan[] = "iiiriirirrrr";42    int next = 0;43    printf("served");44    for (int s = 0; plan[s] != '\0'; s++) {45        if (plan[s] == 'i') {46            pq_insert(&q, jobs[next]);47            next++;48        } else {49            struct job j = pq_remove(&q);50            printf(" %d", j.id);51        }52    }53    printf("\n");54    printf("insert work %d, remove work %d\n", insert_work, remove_work);55    return 0;56}

The interface

A priority queue holds items that each carry a priority, and always hands out the most urgent one next, whatever order they came in. It has three operations:

• insert: add an item with its priority.
• remove: take out the most urgent item and return it.
• peek: look at the most urgent item without taking it out.

Here, as later with heaps, a smaller number is more urgent: priority 1 comes before priority 2. A plain queue is the special case where the priority is the time of arrival.

A job here is a priority and an id:

struct job {
    int priority;
    int id;
};

struct pq {
    struct job items[CAP];
    int size;
};

With CAP 16, sizeof (struct job) is 8 bytes and sizeof (struct pq) is 16 × 8 + 4 = 132. In the clip, q sits at 0x7f60, on a multiple of 16 because it holds an array: items[k].priority is at 0x7f60 + 8k, its id 4 bytes after, and size at 0x7fe0.

The code and its cost

Both versions below keep the jobs in an array, as in the array lessons; the difference is whether the array is kept in order. As in Stacks, checks for a full or empty queue are left to the caller. Two static counters, insert_work and remove_work, count each job looked at or moved.

Unsorted: the work is in remove

void pq_insert(struct pq *q, struct job j)
{
    q->items[q->size] = j;
    q->size++;
}

struct job pq_remove(struct pq *q)
{
    int best = 0;
    for (int i = 1; i < q->size; i++) {
        remove_work++;
        if (q->items[i].priority < q->items[best].priority)
            best = i;
    }
    struct job j = q->items[best];
    q->size--;
    q->items[best] = q->items[q->size];
    return j;
}

Insert puts the job in the next free cell: a fixed few steps. Remove compares every waiting job with the best so far, then fills the gap with the last job, so the waiting jobs stay in cells 0 to size − 1. Order is not kept, and nothing needs to be.

The six jobs, with priorities 4, 9, 2, 7, 1, 5, arrive and leave by the plan iiiriirirrrr: i for an arrival, r for serving one.

served 3 5 1 6 4 2
insert work 0, remove work 11

The six scans compare 2, 3, 3, 2, 1 and 0 times: one fewer than the jobs waiting.

Sorted: the work is in insert

Keep the array with the most urgent job last, and remove becomes a fixed few steps:

void pq_insert(struct pq *q, struct job j)
{
    int i = q->size;
    while (i > 0) {
        insert_work++;
        if (q->items[i - 1].priority > j.priority)
            break;
        q->items[i] = q->items[i - 1];
        insert_work++;
        i--;
    }
    q->items[i] = j;
    q->size++;
}

struct job pq_remove(struct pq *q)
{
    q->size--;
    return q->items[q->size];
}

Insert starts from the end and slides each more urgent job one cell right, the same shifting as inserting into the middle of an array, until it meets a less urgent job. Peek is just the last cell. A job equal in priority to one waiting slides it too, so it lands in front of it and is served after it: equal priorities are served first come, first served. These six jobs have no ties.

The same plan gives the same order served, with the work moved:

served 3 5 1 6 4 2
insert work 10, remove work 0

That is 7 comparisons and 3 slides.

What it costs

Peek costs what remove does, without taking the job out: a scan unsorted, the last cell sorted.

For n inserts and then n removals, either way costs up to about n²/2 steps: the unsorted scans always compare n − 1, n − 2, …, 0 times, and the sorted inserts slide up to 0, 1, …, n − 1 jobs. On arrivals in random order, a sorted insert slides about half the waiting jobs, so the sorted version averages about n²/4. A heap, the subject of a later chapter, does both insert and remove in about log₂ n steps.

Worked example

Which job is served first? Job 3, priority 2. Job 5, with priority 1, is more urgent, but it has not arrived yet when the first r comes.

In the sorted version, where is the most urgent job? In the last cell, size − 1.

A thousand jobs. Insert 1,000 jobs, then remove them all, unsorted. The scans compare 999 + 998 + … + 1 + 0 = 499,500 times.

The heap’s count. A heap of 1,000 jobs makes at most 9 swaps per operation, the whole part of log₂ 1,000 ≈ 9.97. For the 2,000 operations that is at most 18,000, against 499,500.

Many peeks. With few arrivals and many peeks, sorted storage wins: every peek reads the last cell, while unsorted storage scans all n each time.

Where it’s used

Task schedulers. An operating system runs the most urgent ready task next; a print or network queue may let urgent jobs jump ahead.

Event-driven simulation. A simulator keeps future events by their time and always runs the earliest next: the priority is the time.

Shortest paths. The shortest-path algorithm of the graph chapter always extends the nearest unfinished place next, taken from a priority queue.

Merging sorted files. To merge k sorted files, keep the front item of each in a priority queue and take the smallest each time.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.