Heaps & Priority Queues

A binary heap is a complete binary tree that satisfies the heap invariant: in a min-heap, every node is ≤ its children, so the smallest element sits at the root; a max-heap flips the inequality. The invariant is local — it says nothing about siblings — which is exactly why a heap gives you the min/max in O(1) but leaves the rest only partially ordered.

Array representation

Because the tree is complete (filled left-to-right, every level full except possibly the last), it packs into an array with no pointers. For a node at index i:

        1                index:  0  1  2  3  4  5
     / \               value:  1  3  2  7  8  5
    3   2
   / \  /              parent(i) = (i - 1) / 2
  7  8 5               left(i)   = 2i + 1
                       right(i)  = 2i + 2

The two repair operations

• sift-up (used by insert): append at the end, then swap with the parent while it violates the invariant. O(log n).
• sift-down (used by extract-min): move the last element to the root, then swap with the smaller child while it violates the invariant. O(log n).

Build-heap is O(n)

Naively inserting n elements is O(n log n). But heapify-in-place — sift-down from the last internal node up to the root — is O(n). Most nodes are near the leaves and sift down only a level or two; the cost telescopes to a constant times n (see the dedicated question).

What heaps unlock

• Heap sort — build a max-heap, then repeatedly swap the root to the end and sift-down the shrunken heap. O(n log n), in-place, not stable.
• Top-K — a heap of size k keeps the running winners in O(n log k), far cheaper than a full sort when k ≪ n.
• Streaming median — a max-heap of the lower half and a min-heap of the upper half, kept balanced, give the median in O(1) with O(log n) inserts.