Min-Heaps and Priority Queues

Introduces the priority queue abstract data type and its standard implementation as a binary min-heap. Covers the array representation with parent/child index formulas, the min-heap property, and the two core operations: insert (sift-up) and extract-min (sift-down). These are the building blocks used to efficiently select the next airport, flight, or route to process in shortest-path algorithms.

Step 1 of 157%

Tutorial

Priority Queues and the Min-Heap Property

In flight routing, we constantly need to ask "which option has the smallest cost right now?" — the shortest-delay flight, the next-departing aircraft, the closest unvisited airport. A priority queue is the data structure that answers this efficiently.

A priority queue supports three operations:

$\texttt{insert}(x)$ : add the element $x$
$\texttt{peek-min}()$ : return the smallest element
$\texttt{extract-min}()$ : remove and return the smallest element

The standard implementation is a min-heap: a complete binary tree (filled level by level, left to right) in which every node's value is less than or equal to the values of its children. The smallest element therefore always sits at the root.

We store the heap as an array $H[0], H[1], \ldots, H[n-1]$ , level by level. With $0$ -based indexing, the node at index $i$ has:

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

The min-heap property requires $H[\text{parent}(i)] \le H[i]$ for every $i \ge 1$ .

For example, consider $H = [2, 5, 3, 9, 7, 4]$ . Checking each child against its parent:

$i=1$ : $H[0]=2 \le 5 = H[1]$ ✓
$i=2$ : $H[0]=2 \le 3 = H[2]$ ✓
$i=3$ : $H[1]=5 \le 9 = H[3]$ ✓
$i=4$ : $H[1]=5 \le 7 = H[4]$ ✓
$i=5$ : $H[2]=3 \le 4 = H[5]$ ✓

All checks pass, so this is a valid min-heap.