How Priority Queues Actually Work

A priority queue has one job: hand back the highest-priority item you've got, cheaply, even as new items keep arriving in between. Scanning every element to find the max each time is O(n) per call. Keeping the whole collection fully sorted makes lookup free but turns every insert into an O(n) shifting operation. A heap gets both insert and remove-the-max down to O(log n) — and does it with nothing more exotic than a plain array.

No pointers — just index arithmetic

A heap is a complete binary tree — every level fully filled before the next one starts — and that one constraint is what lets it skip pointers entirely. Store it as a flat array and a node's parent and children fall straight out of its index: parent(i) = ⌊(i-1)/2⌋, left(i) = 2i+1, right(i) = 2i+2. Insert 50, 30, 70, 20, 40, 60, 80 one at a time into a max-heap and this is the array you get:

The only invariant a heap actually enforces is parent beats child — 80 ≥ 40 and 70, 40 ≥ 20 and 30, 70 ≥ 50 and 60. Notice what's missing: 40 and 70 aren't ordered relative to each other, and neither are 20/30 versus 50/60. A heap is deliberately not a fully sorted structure — it's exactly sorted enough to always know the max, and not one comparison more.

Insert: push to the end, then sift up

A new value always starts at the next open array slot — the bottom of the tree — then swaps upward with its parent for as long as it violates the heap property. Insert 80 into [70, 40, 60, 20, 30, 50]:

insert 80 at index 6           -> [70, 40, 60, 20, 30, 50, 80]
80 > parent 60 (index 2) — swap -> [70, 40, 80, 20, 30, 50, 60]
80 > parent 70 (index 0) — swap -> [80, 40, 70, 20, 30, 50, 60]
at the root — done

Two swaps, each one level up — that's sift-up, and its worst case is bounded by the tree's height, which is log₂ n for a complete tree. That bound is the entire reason a heap beats a sorted array here: a sorted array's insert has to shift every element after the insertion point, which is O(n) in the worst case, not O(log n).

Extract: swap the last element to the root, then sift down

You can't just delete the root outright — that would leave a hole and break the complete-tree shape the whole index arithmetic depends on. The actual move: save the root as the value to return, move the last element into the root's spot, shrink the array by one, then let that displaced value sink to wherever it belongs:

extract from [80, 40, 70, 20, 30, 50, 60]
save root 80, move last (60) to root -> [60, 40, 70, 20, 30, 50]
60 vs children 40, 70 — 70 wins — swap -> [70, 40, 60, 20, 30, 50]
60 vs child 50 (only child left) — 60 already larger — settled
return 80

That's sift-down: at each step, swap with whichever child actually outranks the current value (not just any child that does — the higher-priority one, since swapping with the wrong child could re-violate the property one level down). Same O(log n) bound as insert, same reason — bounded by tree height.

Peek is the one truly free operation

Reading the current max costs nothing beyond reading array[0] — no comparisons, no swaps, O(1). This is the payoff for keeping only the weak parent-beats- child invariant instead of a full sort: the one query a priority queue exists to answer fast is answered by definition, for free, every time.

Min-heap and max-heap are the same algorithm

Every comparison above is really "does this value outrank that one," and flipping a single comparator — < instead of > — turns the exact same insert and extract logic into a min-heap instead of a max-heap. Nothing else about the structure changes.

Where this shows up

• Dijkstra's algorithm uses a min-heap to always process the closest unvisited node next — see BFS vs DFS for the unweighted version of that same "what do I process next" problem, and why weighted edges need a different algorithm entirely.
• OS task schedulers use a priority queue to pick the next process to run without re-sorting the entire run queue on every context switch.
• Top-K problems — "find the 10 largest values in a huge stream" — keep a heap of size 10 rather than sorting everything, since a heap only ever needs to know its current extreme.
• Heap sort builds a heap from the whole array, then repeatedly extracts the max into the end of the array — O(n log n), in place, no extra memory.

Try it yourself

Heap Visualizer runs insert, extract, and peek on a real heap, step by step — toggle between min-heap and max-heap and watch sift-up and sift-down swap exactly the nodes described here, one comparison at a time. Runs entirely in your browser.