Priority queue

Prerequisites

• Queue.
• Binary trees stored in arrays: children of $i$ at $2i+1$, $2i+2$ (see Trees).
• Logarithms.

The analogy

How it works

Start with a sequence of operations by hand

The queue is a min-heap in an array: every parent is ≤ its children, and the parent of index $i$ is $\lfloor (i-1)/2 \rfloor$. Insert 5, 3, 8, 1. Predict, then open "Check".

Finish the picture: serving the next item

Now call extract-min on [1, 3, 8, 5].

• Remove the root. Predict what goes to the root first.
  Check

  The last leaf, 5: the array becomes [5, 3, 8] and 1 is returned.

• Sift down. Predict the final heap.
  Check

  5's children are 3 and 8; 3 is smaller and less than 5, so swap: [3, 5, 8]. 5 has no children now: done.

The rule in plain words

Insert: append at the end, then swap upwards while smaller than the parent.

Extract-min: take the root, move the last leaf to the root, then swap it downwards with its smaller child while it is bigger than that child.

The code

Read this code after you have done the inserts by hand. It will make more sense.

typedef struct { int a[100]; int n; } PQ;          /* min-heap in an array */

void pq_insert(PQ *q, int v) {                     /* caller checks n < 100 */
    int i = q->n++;
    q->a[i] = v;
    while (i > 0 && q->a[(i - 1) / 2] > q->a[i]) {  /* sift up */
        int p = (i - 1) / 2, t = q->a[p];
        q->a[p] = q->a[i]; q->a[i] = t;
        i = p;
    }
}

int pq_extract_min(PQ *q) {                        /* caller checks n > 0 */
    int top = q->a[0];
    q->a[0] = q->a[--q->n];                        /* last leaf to the root */
    for (int i = 0;;) {                            /* sift down */
        int s = i, l = 2 * i + 1, r = 2 * i + 2;
        if (l < q->n && q->a[l] < q->a[s]) s = l;
        if (r < q->n && q->a[r] < q->a[s]) s = r;
        if (s == i) break;
        int t = q->a[i]; q->a[i] = q->a[s]; q->a[s] = t;
        i = s;
    }
    return top;
}

flowchart TD
  A["insert v: put it at index n"] --> B{"v smaller than its parent?"}
  B -->|yes| C["swap with parent, move up"]
  C --> B
  B -->|"no, or at root"| D["done: heap order holds"]
          

How fast is it?

The heap is a complete binary tree, so its height, and the most swaps one sift can do, is:

The index rules need no pointers: parent of $i$ is $\lfloor (i-1)/2 \rfloor$, children are $2i+1$ and $2i+2$.

Common mistakes

• Thinking the heap array is sorted and reading the "second smallest" from index 1 (it could be at index 2).
• In sift-down, swapping with the first smaller child instead of the smallest child.
• Forgetting to decrease n before moving the last leaf to the root.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• The minimum is at the root because every parent is ≤ its children.
• Insert and extract-min are $O(\log n)$ because a sift moves along one path of a tree of height $\log_2 n$.
• The heap fits in an array because a complete tree has no gaps, so index arithmetic replaces pointers.
• The last leaf moves to the root on extract because that keeps the tree complete.
• Searching is $O(n)$ because heap order only relates parents to children, not siblings.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. How is a priority queue like an emergency room?
   Sample answer

   Patients are seen by urgency, not arrival time. A priority queue always returns the most urgent item, here the smallest key.

2. Walk through inserting 5, 3, 8, 1 into a min-heap.
   Sample answer

   [5]; 3 swaps up → [3, 5]; 8 stays → [3, 5, 8]; 1 swaps with 5 then with 3 → [1, 3, 8, 5].

3. Why does the sift-up loop compare with a[(i - 1) / 2]?

   A good answer names that index.

   Sample answer

   That is the parent of index i in an array-stored complete binary tree, and the heap rule compares each node with its parent.

4. So what is a priority queue, in one sentence?
   Sample answer

   A collection where you can insert items at any time and always remove the one with the highest priority, typically implemented as a binary heap.

5. Why are insert and extract-min $O(\log n)$?

   A good answer mentions the height of the tree.

   Sample answer

   Each sift moves one item along a single root-to-leaf path, and a complete binary tree with $n$ nodes has height about $\log_2 n$.

6. What do insert, extract-min, peek and search cost?
   Sample answer

   insert and extract-min $O(\log n)$, peek $O(1)$, search for an arbitrary value $O(n)$.

7. Why not just keep a sorted array?
   Sample answer

   Extracting the minimum would be cheap, but every insert would shift elements, costing $O(n)$. A heap keeps both operations at $O(\log n)$.

8. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
   Sample answer

   I'd leave out the index formulas and the $O(n)$ build. I'd keep the emergency-room analogy, the four inserts with 1 rising to the top, and "smallest first, $O(\log n)$ per operation".

External resources

• VisuAlgo: Binary heap: animate insert and extract on a priority queue.
• GeeksforGeeks: Priority queue: implementations compared.
• Wikipedia: Priority queue: operations, implementations and applications.
• MIT OCW 6.006: lecture on binary heaps and priority queues.

Videos

• YouTube search: binary heap priority queue: pick a walkthrough of sift up and sift down.