Stacks, Heaps and Priority Queues

Who is next?

An emergency department scores every arriving patient for urgency. All day, two things happen: a patient arrives with a score, and a doctor becomes free and takes the most urgent patient waiting. A busy department sees thousands of arrivals a day, and "who is next?" is asked as often as the queue grows.

Module 13 gave you a structure that keeps every key in order while keys arrive and leave. It would work here: the most urgent patient is the largest key, one path from the root away. But the triage desk never asks for the third most urgent patient, or for everyone between two scores. It asks one question, over and over: which is the largest? This module is about structures that answer only "what comes next?", and are cheaper and simpler because they promise nothing else.

There are two common meanings of "next". The most recent item is the job of a stack. The most important item is the job of a heap, and of std::priority_queue, which is a heap inside a vector. You will see both, why each costs what it costs, and one surprise: a heap can be built from n keys in linear time, faster than inserting them one at a time.

A sorted container does more than asked

Keep the waiting scores in an unsorted std::vector and an arrival costs one push_back. Finding the most urgent patient means looking at every score, so with 2,000 waiting, each "who is next?" costs 1,999 comparisons.

Keep them sorted, largest at the back, and "who is next?" is back(). Now each arrival must be placed: a halving search finds the place in about 11 comparisons, but every score after it moves one slot, about 1,000 on average.

A balanced search tree does both in $O(\log n)$, but it pays for promises the desk never uses: a node allocated per patient, pointers, rebalancing, and complete order. What "who is next?" really needs is weaker than sorted order. The largest score must be easy to find, and it must be cheap to repair the structure when the largest leaves or a new score arrives.

The most recent: a stack

A stack hands back the item added most recently: last in, first out. std::stack<T> offers push, top, pop, empty and size, and nothing else; it cannot be indexed or iterated. It is an adaptor: it wraps another container, std::deque<T> unless you name one, and exposes only the operations a stack should have. All of them are constant time.

An editor's undo history is a stack. Each edit is pushed; undo takes the most recent one off.

#include <stack>
#include <string>

int main() {
    std::string text;
    std::stack<std::string> history;          // what the text was before each edit
    for (const char* word : {"heap", "s", " and", " stacks"}) {
        history.push(text);
        text += word;
    }
    text = history.top();                     // undo " stacks"
    history.pop();
    text = history.top();                     // undo " and"
    history.pop();
    return text == "heaps" && history.size() == 2 ? 0 : 1;
}

Module 11 used the stack's opposite, std::queue, first in first out, for breadth-first search. The difference in which item comes out next is the whole difference between exploring level by level and diving down one path.

A stack kept in order

A weather station records readings 12, 9, 14, 7, 8, 15, 11, 13 and wants, for each one, the position of the next higher reading to its right. The obvious method starts at each reading and scans right until it finds a higher one. Here that makes 11 comparisons, which is cheap; but on readings that only ever decrease, every scan runs to the end, and the total is $n(n-1)/2$.

A stack does it in one pass, by holding the readings that are still waiting for their answer. Here is the rule. When a new reading arrives, every waiting reading lower than it has found its answer: pop each one and record the new position for it. Then push the new reading, which now waits too.

Why is it correct? A reading is popped exactly when the first higher reading arrives, so its recorded answer is the nearest higher reading to its right. A reading still on the stack at the end has none. And the invariant holds: everything lower than the newcomer was just popped, so the newcomer is lower than whatever is left beneath it.

The most urgent: a heap

A binary heap is a binary tree with two rules. The first is about shape: the tree is complete, so every level is full except perhaps the last, which fills from the left. The second is about order.

Compare it with module 13's order invariant. A search tree says where every key must be, relative to every node above it; a heap says only that parents beat children. Siblings can be in either order, and a key on the left can be larger than one on the right. That weakness is the point: there are many valid heaps for the same keys, so repairing one after a change takes little work.

Completeness is what makes a heap cheap to store. Number the nodes level by level, left to right, starting at 0, and store them in that order in a std::vector. No pointers are needed, because positions are arithmetic:

$$\text{parent}(i)=\lfloor (i-1)/2\rfloor ,\text{children}(i)=2i+1,2i+2.$$

Here is the heap the triage desk holds after the scores 31, 74, 52, 18, 90, 66, 45 have arrived, as a tree and as the vector that stores it.

Push: append, then sift up

A new score goes into the only place that keeps the tree complete: the end of the vector, the next free spot on the bottom level. Shape is now right, but order may not be. The new key may be larger than its parent, and only there. So compare it with its parent, and if it is larger, swap the two. The key is now one level higher, and the same question applies again. Stop when it is no larger than its parent, or when it reaches the root. This is sifting up.

Follow 90 arriving at the heap [74, 31, 52, 18]. It is appended at position 4. Its parent, position 1, holds 31: swap. Its parent is now position 0, holding 74: swap. 90 is at the root after two swaps, and the vector reads [90, 74, 52, 18, 31]. Then 66 arrives at position 5, beats its parent 52 at position 2 and swaps once; 45 arrives at position 6 below 66 and stays.

Pop: move the last up, then sift down

The largest key is at position 0, so reading it is free. Removing it leaves a hole at the root, and the only element that can leave without breaking completeness is the last one. So move the last element into the root and shrink the vector. Shape is right again; order may be broken at the root, and only there.

Repair it by sifting down: compare the key with its children, and if either child is larger, swap it with the larger child. The larger child can be the parent of the other one; the smaller child could not. Continue from the key's new position, and stop when no child is larger or the key reaches the bottom.

Popping 90 from [90, 74, 66, 18, 31, 52, 45]: 45 moves to the root, giving [45, 74, 66, 18, 31, 52]. Its children are 74 and 66, so it swaps with 74. At position 1 its children are 18 and 31, both smaller, so it stays: [74, 45, 66, 18, 31, 52]. Popping again returns 74, and 52 sifts down past 66 to give [66, 45, 52, 18, 31].

# The lesson's numbers. heapq is Python's min-heap; its heappush performs exactly the
# sift up described above, so pushing negated scores reproduces the max-heap arrays.
# For the pops, the block checks that each array in the text is a heap with the
# right contents, rather than running a sift down of its own.
import heapq

def is_max_heap(a):
    return all(a[(i - 1) // 2] >= a[i] for i in range(1, len(a)))

arrivals = [31, 74, 52, 18, 90, 66, 45]
h, arrays = [], []
for score in arrivals:
    heapq.heappush(h, -score)
    arrays.append([-x for x in h])
assert arrays[3] == [74, 31, 52, 18]
assert arrays[4] == [90, 74, 52, 18, 31]
assert arrays[6] == [90, 74, 66, 18, 31, 52, 45]
assert all(is_max_heap(a) for a in arrays)

after_first_pop = [74, 45, 66, 18, 31, 52]
after_second_pop = [66, 45, 52, 18, 31]
assert is_max_heap(after_first_pop) and sorted(after_first_pop) == sorted(arrivals)[:-1]
assert is_max_heap(after_second_pop) and sorted(after_second_pop) == sorted(arrivals)[:-2]

# The monotonic stack's answers, by the obvious scan (a stand-in, not the one-pass method).
readings = [12, 9, 14, 7, 8, 15, 11, 13]
def next_higher(i):
    return next((j for j in range(i + 1, len(readings)) if readings[j] > readings[i]), None)
assert [next_higher(i) for i in range(8)] == [2, 2, 5, 4, 5, None, 7, None]
scan = sum(min(len(readings) - 1, next_higher(i) if next_higher(i) is not None else len(readings) - 1) - i
           for i in range(len(readings)))
assert scan == 11
assert 8 + 6 <= 2 * len(readings)

Why both repairs work

Each repair starts from a vector that is a heap everywhere except at one position, and moves that one exception by one level per swap.

During a sift up, the only possible violation is between the moving key and its parent. Swapping them fixes that pair. The parent moves down into a position whose other children were already no larger than it, so nothing new breaks below. The only new question is between the moving key and its new parent, one level up. When the key stops, or reaches the root, no violation is left.

During a sift down, the only possible violation is between the moving key and its children. After a swap with the larger child, that child sits above both the moving key and its former sibling, and it is at least as large as both, so the position the key left is fine. The only new question is below the key's new position. When it stops, or reaches a leaf, no violation is left. Swapping with the smaller child would put the smaller child above the larger one and create a new violation.

Cost is height, and height is fixed

A complete tree holding $n$ keys has exactly $\lfloor {\log }_{2}n\rfloor +1$ levels. There is no bad arrival order: shape is forced, and that is the difference from module 13, where sorted arrival built a chain. A sift up makes at most one comparison and one swap per level. A sift down makes up to two comparisons per level, one to find the larger child and one against it. So push and pop are $O(\log n)$ in the worst case: about 11 levels for the 2,000 waiting patients, and 20 for a million.

Building a heap from n keys

Sometimes all the keys are known at once: last night's waiting list, or a vector to be sorted. Pushing them one at a time costs up to ${\sum }_{i=1}^n\lfloor {\log }_{2}i\rfloor$ comparisons, about $n{\log }_{2}n$, when each key sifts all the way to the root, as increasing keys do in a max-heap.

There is a better order. Treat the whole vector as a complete tree that may be in any order. The leaves, which are the last half of the vector, are already heaps of one key. Then go backwards from the last parent, at position $\lfloor n/2\rfloor -1$, to the root, and sift each one down. When a position is sifted, both of its subtrees are already heaps, so sifting it down makes its own subtree a heap. When the root has been sifted, the whole vector is a heap.

Measure the claim

The table counts comparisons with Python's heapq, a min-heap, standing in for a C++ heap: n pushes of keys arriving in decreasing order (the worst order for a min-heap's sift up), and heapq.heapify, CPython's bottom-up build, on the same keys. The lab measures its own C++ version at other sizes.

class Counted:
    comparisons = 0
    def __init__(self, v): self.v = v
    def __lt__(self, other):
        Counted.comparisons += 1
        return self.v < other.v

def costs(n):
    Counted.comparisons = 0
    h = []
    for x in range(n, 0, -1):
        heapq.heappush(h, Counted(x))
    pushes = Counted.comparisons
    keys = [Counted(x) for x in range(n, 0, -1)]
    Counted.comparisons = 0
    heapq.heapify(keys)
    return pushes, Counted.comparisons

measured = {n: costs(n) for n in (1000, 10000, 100000)}
assert measured == {1000: (7987, 1490), 10000: (113631, 14990), 100000: (1468946, 149988)}
for n, (pushes, built) in measured.items():
    assert pushes == sum(i.bit_length() - 1 for i in range(1, n + 1))   # every key climbs to the root
    assert built <= 2 * n

Pushes per key grow from about 8 to about 15 as $n$ grows a hundredfold, the ${\log }_{2}n$ shape; bottom-up building stays at 1.5 comparisons per key. These are counts for one arrival order and one library, not theorems, but the bound behind them is.

std::priority_queue

std::priority_queue<T> is a heap kept in a std::vector<T>, with push (append, sift up), top (position 0) and pop (sift down). Like std::stack it is an adaptor, and it deliberately has no iteration, no search and no way to change a key's priority in place.

#include <functional>
#include <queue>
#include <vector>

int main() {
    std::priority_queue<int> most_urgent;                                       // largest on top
    std::priority_queue<int, std::vector<int>, std::greater<int>> least_urgent; // smallest on top
    for (int score : {31, 74, 52, 18, 90, 66, 45}) {
        most_urgent.push(score);
        least_urgent.push(score);
    }
    const int first = most_urgent.top();
    most_urgent.pop();
    return first == 90 && most_urgent.top() == 74 && least_urgent.top() == 18 ? 0 : 1;
}

The comparator reads backwards, and it trips almost everyone once. It does not say which element comes out first. It is a "less than" that defines lower priority, and the element on top is one that nothing is greater than. With the default std::less<int>, the largest is on top. With std::greater<int>, "lower priority" means "larger", so the smallest is on top. A custom comparison for structs follows the same rule: return true when the first argument should come out after the second.

The same algorithms work on a vector you own: std::make_heap builds a heap bottom-up in linear time (at most $3n$ comparisons, says the standard), std::push_heap sifts up the last element, and std::pop_heap moves the top to the back and sifts down, after which you pop_back(). Calling pop_heap until the range is empty leaves the vector sorted: that is heapsort, $O(n\log n)$ in the worst case with no extra memory.

Heap or search tree?

Choose a heap when the only question is "which is the largest (or smallest)?", and a search tree when you need any key, a range, the neighbours of a key, or everything in order. A heap gives you a contiguous buffer and no allocation per element, a height that no arrival order can spoil, and linear-time building. A search tree gives you every ordered question in $O(\log n)$. Neither finds an arbitrary key in a heap: a heap has to scan for it, because the invariant says nothing about where a key that is not the largest might be.

A problem that looks different

A simulation of a railway keeps a clock. Each scheduled event (a train arriving, a signal changing) has a time, and handling an event may schedule new events in the future. The clock never ticks second by second: it jumps straight to the earliest scheduled event, handles it, and jumps again. With a million events, what must the simulator hold, which question does it ask before every jump, and what does that question cost per event?

Practise

The lab has you build these structures on its own data. You will answer "nearest taller to the left" for a skyline with a stack whose contents you watch shrink and grow, frame by frame. You will write sift up and sift down for a heap in a vector, with the invariant checked in every frame you record. You will keep the k largest readings of a stream with std::priority_queue, with comparisons counted. Then you will build a heap bottom-up and measure it against pushes at sizes the checks choose. The final challenge tells a story and does not say which structure it needs.

Recap

You can now: use std::stack and std::priority_queue, keep a stack in order for a one-pass answer, store a heap in a vector, push and pop with sift up and sift down, and build a heap in linear time.

Invariant: in a max-heap no node is larger than its parent, so the maximum is at index 0; a monotonic stack holds strictly decreasing values, each waiting for its answer.

Complexity achieved: push and pop make $O(\log n)$ comparisons in the worst case, since a complete tree has $\lfloor {\log }_{2}n\rfloor +1$ levels; bottom-up building is $O(n)$, while n pushes can cost $\sum \lfloor {\log }_{2}i\rfloor$; a monotonic-stack pass makes at most $2n$ stack operations in total.

Failure mode: reading std::priority_queue's comparator as "comes out first" (it means "lower priority"), and swapping with the smaller child when sifting down.

In real software: std::priority_queue is push_heap and pop_heap over a std::vector; std::make_heap is a linear-time bottom-up build, and repeated pop_heap is heapsort.

Retrieval: from module 13, what does a search tree promise that a heap does not, and which of those promises would the triage desk ever use?

Check yourself

1. State the heap invariant, and explain why it puts the largest key at position 0 but says nothing about which child is larger.
2. After a pop moves the last element to the root, why must sifting down swap with the larger child? Give three keys where taking the smaller child breaks the invariant.
3. Why is bottom-up building linear while n pushes are not? Which keys does each method move the furthest?

Original SciMigo course material. C++ examples target C++17.