Heaps & Priority Queues

The most-urgent-first structure

Picture a hospital emergency room. Patients don't get seen in arrival order (that's a queue) or by name (that's a sorted tree) — they're seen by *severity*. The sickest goes next, no matter when they walked in. The abstract tool for this is a [[priority-queue|priority queue]]: you toss items in with a priority, and every time you ask for one you get the highest-priority item available. The data structure that makes this fast is the [[heap|heap]].

A heap is a binary tree with two promises. First, shape: it is a *complete* binary tree — every level is full except possibly the last, which fills left to right with no gaps. Second, the heap property: every parent is ≥ both its children (a *max-heap*) — or ≤, for a *min-heap*. Note this is weaker than a BST: there is no left/right ordering, only the parent-beats-child relationship. That weaker rule is the trade: a heap gives you the single top item instantly, but not a fully sorted view.

A max-heap (every parent >= its children):

           (50)
          /    \
       (30)    (40)
       /  \     /
    (10) (20) (35)

  top is always the maximum (50).
  NOTE: it is NOT left<right -- 30's children 10,20 are fine,
  but a heap makes no promise about order across siblings.

A tree with no pointers: the array trick

Here is the most beautiful idea in this guide. Because a heap is *complete* (no gaps), you can pour it into a flat array level by level, top to bottom, left to right — and the parent/child links become pure arithmetic. No `Node`, no `left`/`right` pointers, no `new`. For the node at index `i`:

tree:        (50)              array (index):
            /    \             0:50 1:30 2:40 3:10 4:20 5:35
         (30)   (40)
         / \    /            for node at index i:
      (10)(20)(35)             left  child = 2*i + 1
                                right child = 2*i + 2
                                parent      = (i - 1) / 2

  index 1 (=30): left=2*1+1=3 (10), right=2*1+2=4 (20). yes!

Push and pop: bubble up, sift down

Two operations keep the heap honest. To push: drop the new value at the end of the array (keeping the complete shape), then *bubble it up* — while it's bigger than its parent, swap with the parent. It climbs at most one level per swap, so it stops within the tree's height. To pop the max: take the root (the answer), move the last element up to the root to keep the shape, then *sift it down* — repeatedly swap it with its larger child until the heap property holds again.

1. top — read the root, `heap[0]`. Nothing moves. O(1).
2. push — append at the end, then bubble up while bigger than the parent. At most one swap per level: O(log n).
3. pop — save the root, move the last element to the front, sift it down. Again one swap per level: O(log n).

std::priority_queue, and a free sort

You rarely hand-roll a heap either — C++ gives you `std::priority_queue`, a max-heap out of the box, with `push`, `top`, and `pop` exactly as described. (Want a min-heap, so the *smallest* surfaces first? Pass a `std::greater<>` comparator.)

#include <queue>
std::priority_queue<int> pq;       // a max-heap
pq.push(30); pq.push(50); pq.push(40);
std::cout << pq.top();             // 50  -- the largest, O(1)
pq.pop();                          // remove 50, O(log n)
std::cout << pq.top();             // 40  -- next largest

// a min-heap (smallest on top):
// std::priority_queue<int, std::vector<int>, std::greater<int>> minpq;

And a lovely callback to the sorting rung: if you push all n items into a heap and then pop them one by one, they come out in sorted order. n pops, each O(log n), is O(n log n) total — the same league as merge sort. That algorithm is [[heapsort|heapsort]], and it's a heap turned into a sorter, in place, with no extra array. The same structure that runs your priority queue can also sort your data.