19. Priority Queues and Heaps

When arrival order is the wrong rule#

A normal queue removes the oldest item. A stack removes the newest. A priority queue removes the item with the highest priority, regardless of arrival time. Hospital triage, scheduling and graph algorithms all involve choosing the most urgent or cheapest available item.

The lecture uses larger numbers as higher priority. Other applications use the opposite direction. Dijkstra chooses the smallest tentative distance, so its natural priority queue is a min-priority queue. The course's existing scan-based Dijkstra remains valid; replacing that scan with a heap changes the implementation and analysis, not the underlying shortest-path argument.

A priority queue is an ADT with four central operations:

• insert(item, priority) adds an occurrence.
• delete() removes and returns the highest-priority item.
• peek() returns that item without removing it.
• isEmpty() reports whether any item remains.

Unlike a map, a priority queue may contain repeated items or equal priorities. Unless its specification adds a tie-breaking rule, equal priorities need not preserve arrival order. Deletion here means deleting the highest-priority item, not an arbitrary item supplied by the caller.

For example, insert Alice at 4, Bob at 3, Andrew at 30 and Jas at 35. Delete returns Jas, then Andrew. Insert Jake at 23 and Sasha at 25. Peek returns Sasha without changing the collection; subsequent deletes return Sasha, Jake, Alice and Bob.

Practice. A FIFO queue receives (A, 2) then (B, 9). What differs if this is a max-priority queue?

Simple implementations and their costs#

Let $n$ be the number of stored occurrences. An unordered array appends in constant time when capacity is available. To find the maximum, it scans up to $n$ priorities. Removal may shift elements; alternatively it can fill the hole with the final element because order is irrelevant. Either way the search gives $O(n)$ deletion.

An array sorted by increasing priority puts the maximum at its end. Peek and deletion are constant-time, but insertion can shift $n$ elements.

For a linked list, unordered insertion at the head is constant-time, but maximum search is linear. A list sorted by decreasing priority puts the maximum at the head: peek/delete are constant-time and insertion is linear.

*Array capacity growth can make an individual insertion $O(n)$; geometric resizing gives amortised growth overhead. The unordered linked-list peek is $O(n)$ without extra maximum-tracking information, matching the lecture's explanation rather than its summary-table typo.

A heap balances insertion and deletion when both happen repeatedly. If you insert everything once and then perform only one maximum query, a linear scan may be simpler and equally appropriate.

Binary heaps: order plus shape#

A max-heap satisfies the heap-order property: every parent's value or priority is at least each child's. Following a path from the root can never increase the value. Consequently the root is at least every descendant and is a maximum.

A binary heap additionally satisfies the completeness property: every level except possibly the last is full, and the last is filled from left to right. “Complete” does not mean “every node has two children”, nor does it require the final level to be full.

The lecture first illustrates a heap with three children per node, then specialises to binary heaps. Binary is the representation used throughout the remaining implementation.

A heap is different from a BST. Heap order compares parents with descendants; it does not place all smaller values left and larger values right. Sibling subtrees need not be sorted relative to each other. A max-heap with root 120 can validly have left child 50 and right child 100.

Store the complete tree in an array#

Completeness means breadth-first order occupies consecutive indices without structural gaps. The lecture's priority queue leaves index 0 unused and puts the root at 1:

$$\operatorname{parent}(i)=\left\lfloor\frac i2\right\rfloor,\qquad \operatorname{left}(i)=2i,\qquad \operatorname{right}(i)=2i+1.$$

The parent rule is used only for $i>1$. A child exists only if its index is at most the current item count.

Reading the diagram, indices 1–7 contain [120, 50, 100, 20, 30, 40, 60]. Index 3 contains 100; its children at 6 and 7 contain 40 and 60. We do not allocate tree nodes or child pointers: arithmetic supplies the links.

With $n\geq1$, the number of levels is $\lfloor\log_2 n\rfloor+1$, and height measured in edges is $\lfloor\log_2n\rfloor$. Full levels contain $1,2,4,\ldots$ nodes. The geometric total through depth $h$ is $2^{h+1}-1$, so doubling the number of nodes increases the height by about one. This is why a root-to-leaf repair costs logarithmic time without rotations.

Practice. In a one-based heap with six items, which children exist for index 3? Why is searching for an arbitrary value not necessarily logarithmic?

Insertion: fix up the new leaf#

Insertion must preserve both shape and order. Append the item at the next free array position: this preserves completeness. Only the relation to its parent may now violate heap order.

Fix up repeatedly compares the new item with its parent. If larger, swap them and continue from the parent's index. Stop at the root or when the parent is at least the item.

Insert 26 into lecture heap [20, 17, 11, 13, 1, 8]:

1. Append at index 7, the right child of index 3: [20,17,11,13,1,8,26].
2. Compare 26 with its parent 11. Swap indices 7 and 3: [20,17,26,13,1,8,11].
3. Compare 26 with root 20. Swap indices 3 and 1: [26,17,20,13,1,8,11].
4. The item is at the root, so stop.

Why does this work? Before insertion every old subtree is a heap. The only possible disorder lies along the new leaf's ancestor path. When the larger item swaps upward, the former parent moves down into a subtree whose existing descendants it already dominated. The possible violation moves one level upward. Once it has no smaller parent, the whole heap is valid.

The following custom player uses zero-based array positions to show the same values. Its pseudocode and table name that representation explicitly; convert by subtracting one from the one-based indices above.

Appending costs $O(1)$ with spare capacity. Each swap moves one level upward, so worst-case repair is $O(\log n)$ and best case $O(1)$. Iterative fix-up uses $O(1)$ auxiliary space.

The C tab shows this zero-based fix-up, separate from the later one-based priority-queue implementation. The caller first appends the item at index i; fixUp0 moves it upward until the parent is large enough. For the seven-item trace, the parent indices are (6-1)/2=2 and (2-1)/2=0. The code uses i > 0 before calculating (i-1)/2, so unsigned size_t never underflows.

#include <stddef.h>

/* A zero-based max-heap; the new item is already appended at i. */
void fixUp0(int a[], size_t i) {
    while (i > 0) {
        size_t parent = (i - 1) / 2;
        if (a[parent] >= a[i]) break;
        int tmp = a[parent];
        a[parent] = a[i];
        a[i] = tmp;
        i = parent;
    }
}

Practice. Insert 10 into [20,17,11,13,1,8]. How many swaps occur?

Delete the maximum: fix down#

Save the root for the return value. Replace it with the last item and reduce the item count. Removing the final position preserves completeness; heap order may now be violated at the root.

Fix down compares the item with its largest existing child. If that child is larger, swap and continue down. Choosing the largest child is essential: choosing the smaller one could leave a larger sibling above its new parent.

Delete 20 from [20,17,11,13,1,8]:

1. Save 20, move 8 to the root, remove the last position: [8,17,11,13,1].
2. Of root children 17 and 11, choose 17. Swap: [17,8,11,13,1].
3. Of 8's children 13 and 1, choose 13. Swap: [17,13,11,8,1].
4. 8 is now a leaf. Return the saved 20.

At each iteration both child subtrees are already heaps. Promoting the larger child makes the parent dominate both immediate children. Only the position receiving the displaced item may remain invalid. The violation travels down until a leaf or an ordered parent is reached.

For a singleton, deletion leaves an empty heap and no fix-down is needed. Deleting from an already empty priority queue must follow its API contract, such as returning a failure status.

Practice. At a parent with value 4 and children 7 and 9, why swap with 9?

A complete heap-based priority queue#

Items and priorities are separate. The example copies integer items, owns its dynamically allocated array, and gives no arrival-order guarantee for ties.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

struct pqItem { int item, priority; };
struct pq {
    struct pqItem *items;  /* Index 0 is unused. */
    size_t size, capacity;
};

static void pqSwap(struct pqItem *a, struct pqItem *b) {
    struct pqItem tmp = *a;
    *a = *b;
    *b = tmp;
}

struct pq *pqNew(void) {
    struct pq *q = malloc(sizeof *q);
    if (q == NULL) return NULL;
    q->size = 0;
    q->capacity = 4;
    q->items = malloc((q->capacity + 1) * sizeof *q->items);
    if (q->items == NULL) { free(q); return NULL; }
    return q;
}

bool pqInsert(struct pq *q, int item, int priority) {
    if (q->size == q->capacity) {
        size_t maxSlots = SIZE_MAX / sizeof *q->items;
        if (maxSlots == 0 || q->capacity > (maxSlots - 1) / 2)
            return false;
        size_t capacity = 2 * q->capacity;
        struct pqItem *items =
            realloc(q->items, (capacity + 1) * sizeof *items);
        if (items == NULL) return false;
        q->items = items;
        q->capacity = capacity;
    }
    size_t i = ++q->size;
    q->items[i] = (struct pqItem){item, priority};
    while (i > 1 && q->items[i].priority > q->items[i / 2].priority) {
        pqSwap(&q->items[i], &q->items[i / 2]);
        i /= 2;
    }
    return true;
}

bool pqPeek(const struct pq *q, int *out) {
    if (q->size == 0) return false;
    if (out != NULL) *out = q->items[1].item;
    return true;
}

bool pqDelete(struct pq *q, int *out) {
    if (!pqPeek(q, out)) return false;
    q->items[1] = q->items[q->size--];
    size_t i = 1;
    while (i <= q->size / 2) {
        size_t child = 2 * i;
        if (child < q->size &&
            q->items[child + 1].priority > q->items[child].priority)
            child++;
        if (q->items[i].priority >= q->items[child].priority) break;
        pqSwap(&q->items[i], &q->items[child]);
        i = child;
    }
    return true;
}

bool pqIsEmpty(const struct pq *q) { return q->size == 0; }

void pqFree(struct pq *q) {
    if (q == NULL) return;
    free(q->items);
    free(q);
}

realloc may move the array; updating q->items only on success preserves the old allocation on failure. The capacity overflow check includes the unused index 0. The child loop uses i <= size / 2 so it checks for a left child before computing its index.

Ordinary insertion and deletion are worst-case $O(\log n)$. A growth-triggering insertion also copies $O(n)$ items; across geometrically growing capacity, this gives amortised $O(\log n)$ insertion including resizing. Peek/is-empty are $O(1)$. Storage is $O(n)$ while the capacity remains within a constant multiple of the maximum size retained; this implementation does not shrink after deletion. Iterative repairs require $O(1)$ auxiliary space.

Heapsort: use the array as both heap and output#

Heapsort builds a max-heap inside the input array, then repeatedly moves its maximum to the end. The heap shrinks from the right while a sorted suffix grows there.

An ordinary C array starts at index 0, so the lecture switches formulas:

$$\operatorname{left}(i)=2i+1,\quad \operatorname{right}(i)=2i+2,\quad \operatorname{parent}(i)=\left\lfloor\frac{i-1}{2}\right\rfloor.$$

Use the parent only for $i>0$. Do not mix these with the one-based priority queue.

Two ways to build a heap#

Repeated insertion. Treat the first item as a one-item heap. For each later index, fix that item up within the growing prefix. On [3,5,1,6,7,2,4], the prefix states are:

The total is at most $\sum_{i=1}^n O(\log i)=O(n\log n)$; ascending inputs can force many long upward paths.

Bottom-up heapify. Leaves are already one-node heaps. Start at the last parent, index $\lfloor n/2\rfloor-1$, and fix down each parent in reverse order. Both its child subtrees have already been repaired, so fix-down's precondition holds.

For the lecture input [3,5,4,6,7,2,1]:

1. Index 2 holds 4 above children 2 and 1; no swap.
2. Index 1 holds 5 above 6 and 7; swap with 7, yielding [3,7,4,6,5,2,1].
3. Index 0 holds 3 above 7 and 4; swap with 7, then compare 3 with 6 and 5 and swap with 6.
4. The heap is [7,6,4,3,5,2,1].

Why bottom-up construction is linear#

Saying “$n$ repairs, each $O(\log n)$” gives a valid but loose upper bound. Most repairs cannot travel $\log n$ levels: about half the nodes are leaves, about a quarter have height 1, about an eighth height 2, and so on.

Grouping work by subtree height gives an upper bound proportional to

$$n\sum_{h=0}^{\infty}\frac{h+1}{2^{h+1}}=2n.$$

The geometric series converges to a constant, so heapify is $O(n)$. It also inspects a linear number of parents/children, giving $\Theta(n)$ construction for this implementation. The lecture marks the geometric proof as optional; the distinction between linear bottom-up construction and insertion-based construction is essential.

The slide that calls “this implementation of heapsort” $O(n)$ refers to heapify only. Extracting all maxima still takes $O(n\log n)$.

Practice. Why start heapify at n / 2 - 1 instead of the last index?

Extraction and the sorted suffix#

Starting with [7,6,4,3,5,2,1], swap root 7 with the last item 1. Exclude the last position from the heap, leaving [1,6,4,3,5,2 | 7]. Fix down 1: promote 6, then 5, yielding [6,5,4,3,1,2 | 7].

Next extract 6: swap it with 2, shrink, and repair to [5,3,4,2,1 | 6,7]. The suffix is ascending because each new maximum belongs immediately before the larger maxima already removed.

The invariant is: the prefix is a max-heap; the suffix is sorted; every prefix item is at most every suffix item. A root/end exchange extends the suffix by its next largest value; fix-down restores the prefix heap without touching the suffix. When only one heap item remains, the entire array is sorted.

This built-in uses exactly the zero-based, bottom-up max-heap variant. Follow the tree/array indices, larger-child decisions and separately displayed sorted output.

Complete in-place heapsort in C#

Here n is a count, not the last valid index. Keeping that convention throughout prevents subtracting one twice.

#include <stddef.h>

static void hsSwap(int *a, int *b) {
    int t = *a; *a = *b; *b = t;
}

static void hsDown(int a[], size_t i, size_t n) {
    while (i < n / 2) {
        size_t child = 2 * i + 1;
        if (child + 1 < n && a[child + 1] > a[child]) child++;
        if (a[i] >= a[child]) break;
        hsSwap(&a[i], &a[child]);
        i = child;
    }
}

void heapSort(int a[], size_t n) {
    for (size_t i = n / 2; i > 0; i--)
        hsDown(a, i - 1, n);
    for (size_t end = n; end > 1; end--) {
        hsSwap(&a[0], &a[end - 1]);
        hsDown(a, 0, end - 1);
    }
}

The descending size_t loop tests i > 0 before subtracting. A loop testing i >= 0 would never terminate for an unsigned index. Empty and singleton inputs require no swaps.

Construction is $\Theta(n)$. Extraction has $n-1$ repairs of at most logarithmic depth, giving $O(n\log n)$ total; worst-case and usual average-case are $\Theta(n\log n)$. For all equal values, this early-stopping version can take $\Theta(n)$ because every downward repair stops immediately. It is not adaptive to an already ascending array: being sorted does not provide the heap algorithm with a generally faster route.

Heapsort is in place with $O(1)$ auxiliary space, but unstable: long-distance exchanges may reverse equal-key occurrences. If equal keys must preserve original order, choose a stable algorithm or include original position in the comparison key.

Practice. Suppose labelled values [2a, 2b, 1] compare only by number. How can heapsort reverse the two 2s?

More exam-style practice#

Work each prompt before opening its answer. State the invariant or cost assumption that makes your reasoning valid.

Question 1. A max-heap array is [9,7,8,2,5,6]. Insert 10 and show the swaps needed to restore order.

Question 2. Delete the maximum from [9,7,8,2,5,6]. Which value replaces the root, and where does it end after fix-down?

Question 3. Why is building a heap by repeated insertion O(n log n) but bottom-up heap construction O(n)?

For graph applications see 15. Directed Graph Algorithms and Shortest Paths. For string-key organisation, continue to 20. Tries.