A priority queue always hands you the most important item next — not the one that arrived first. 'Important' is whatever ordering you choose: smallest value, earliest deadline, shortest distance. It's the data structure behind task schedulers, Dijkstra's shortest paths, and event simulations, and it's almost always built on a heap.
Why a heap, not a sorted list
You *could* keep items fully sorted, but then every insert costs O(n) to slot into place. A min-heap is the smarter backing: a binary tree where every parent is smaller than its children, so the smallest (highest-priority) value sits at the root — always one peek away in O(1). The heap isn't fully sorted; it just guarantees the *top*, which is all a priority queue needs.
Stored as an array, no pointers
A heap is a *complete* tree (filled level by level), so it packs perfectly into a plain array. The node at index i finds its children at 2i+1 and 2i+2, and its parent at (i−1)/2. No node objects, no pointers — just index arithmetic.
Insert sifts up, extract sifts down
1Insert: append the new item at the end (the next leaf), then sift up — swap it with its parent while it's smaller — until heap order holds.
2Peek: read the root. O(1), no change.
3Extract-min: take the root (the answer), move the last leaf into the root slot, then sift down — swap it with its smaller child — until order is restored.
Both sift moves walk a single path between root and leaf, so they touch only about log n nodes — the tree's height. That's why insert and extract are O(log n).
Min-heap vs max-heap is one comparison
A min-heap keeps the smallest on top; a max-heap the largest. The structure and the sift logic are identical — only the comparison flips. Need 'largest = highest priority'? Use a max-heap, or push negated values into a min-heap.
OperationTimeSpace
peek (find min) · the rootO(1)O(1)
insert · sift up one pathO(log n)O(1)
extract-min · sift down one pathO(log n)O(1)
Check yourself
Why does a priority queue use a heap instead of keeping all items fully sorted?
