Heaps & Priority Queues: The Array-Backed Tree Behind 'Always Get the Smallest'

In plain words

Imagine a tournament bracket where the best (or worst) player always bubbles to the top. After each round, whoever won the most recent match moves up; if someone leaves, the last person in the bracket slides to the top spot and immediately competes downward until they find their rightful level. That's a heap: a structure where the best (min or max) element is always instantly available at the front, and adding or removing one costs only O(log n) 'match comparisons'. It's the engine behind every 'serve the most urgent task next' system.

A balanced BST keeps every key in full sorted order — powerful, but more than many problems need. Often you only ever ask one question: *what's the smallest (or largest) item right now?* A scheduler wants the highest-priority task; Dijkstra's algorithm wants the nearest unvisited node; a 'top 10' feature wants the largest few. The heap answers exactly that question in O(1), and by demanding only partial order it earns a beautiful bonus: it needs no pointers at all, living entirely inside an array.

The heap property and the array trick

A min-heap is a complete binary tree (every level full except the last, which fills left-to-right) obeying the heap property: every node's key is ≤ both its children's keys. That's strictly weaker than a BST — there's no left/right ordering, only parent-below-children — so the *minimum is always the root*, but siblings are unordered and you cannot search the interior efficiently. A max-heap flips the comparison; everything below is symmetric.

Because the tree is complete, it has no gaps — so you can lay it out level by level in an array and compute relationships by index instead of storing pointers. For a node at index i (0-based): left child = 2i+1, right child = 2i+2, parent = (i−1)/2 rounded down.

Tree view:                  Array view:
                                 idx:  0  1  2  3  4  5
          1                     arr: [1, 3, 2, 7, 4, 5]
         / \
        3   2                  Index arithmetic (0-based):
       / \ /                    parent(i)    = (i-1) // 2
      7  4 5                    left_child(i)  = 2*i + 1
                                right_child(i) = 2*i + 2

Verification:
  arr[0]=1 → children arr[1]=3, arr[2]=2  → 1 ≤ 3, 1 ≤ 2 ✓
  arr[1]=3 → children arr[3]=7, arr[4]=4  → 3 ≤ 7, 3 ≤ 4 ✓
  arr[2]=2 → child    arr[5]=5            → 2 ≤ 5         ✓

The two repair operations

Every heap operation is one of two 'bubbling' fixes that restore the heap property after a local violation:

1. sift-up (bubble-up): used after inserting at the end. While the new node is smaller than its parent, swap them and move up. It rises until it's ≥ its parent or reaches the root. At most h = O(log n) swaps.
2. sift-down (bubble-down / heapify): used after removing the root. While a node is larger than its smaller child, swap with that smaller child and move down. It sinks until both children are ≥ it or it's a leaf. At most O(log n) swaps.

Start (insert 0 at end, index 5):
arr: [1, 3, 2, 7, 4, 0]

Tree:        1
            / \
           3   2
          / \ /
         7  4 0   ← 0 violates heap property (0 < parent 2)

Step 1: swap 0 and its parent 2 (indices 5,2):
arr: [1, 3, 0, 7, 4, 2]
Tree:        1
            / \
           3   0   ← 0 < parent 1? Yes → keep bubbling
          / \ /
         7  4 2

Step 2: swap 0 and parent 1 (indices 2,0):
arr: [0, 3, 1, 7, 4, 2]
Tree:        0
            / \
           3   1   ← 0 is root, done.
          / \ /
         7  4 2

2 swaps total (= height of subtree). O(log n).

push and pop, built from those two

1. push(x): append x at the array's end (keeps the tree complete), then sift-up to restore order. O(log n).
2. peek(): return array[0] — the minimum. O(1), no modification.
3. pop() (extract-min): save array[0] as the answer; move the *last* element to index 0 (keeping the tree complete); shrink by one; sift-down from the root. O(log n).

Step 1: Save arr[0]=1 as the result (minimum).
Step 2: Move last element (5) to root → arr: [5, 3, 2, 7, 4]

Tree:     5
         / \
        3   2
       / \
      7   4

Step 3: Sift-down from root (5).
  Children of 5: 3 (left), 2 (right). Smaller = 2.
  5 > 2 → swap → arr: [2, 3, 5, 7, 4]

Tree:     2
         / \
        3   5
       / \
      7   4

  Children of 5: 7 (left), 4 (right). Smaller = 4.
  5 > 4 → swap → arr: [2, 3, 4, 7, 5]

Tree:     2
         / \
        3   4
       / \
      7   5

  5 is now a leaf (no children). Done.

Result: 1 extracted. Heap: [2, 3, 4, 7, 5]

Building a heap: the O(n) surprise

To heapify an existing array, you might push all n elements one by one: O(n log n). But there's a faster way — sift-down every node from the last non-leaf up to the root, i.e., from index (n/2 − 1) down to 0. This is O(n), not O(n log n), and the reason is a lovely counting argument: most nodes are near the bottom and sift down only a level or two. Summing (nodes at each height) × (their sift-down cost) telescopes to a constant times n. So building a heap from scratch is O(n) — genuinely surprising, and the foundation of heapsort's linear build phase in Lesson 19.

function buildHeap(arr):
    n = len(arr)
    // Leaves are at indices n//2 to n-1; skip them.
    // Start from the last non-leaf, work up to root.
    for i from (n // 2 - 1) down to 0:
        siftDown(arr, i, n)

// Why O(n)?
// Height h has at most n / 2^(h+1) nodes.
// Each node at height h sifts down at most h levels.
// Total work = Σ (h=0 to log n) h * n/2^(h+1)
//            = n * Σ h/2^(h+1)
//            = n * 2  (geometric series)  = O(n)

Complexity summary

Priority queues and their applications

• Dijkstra's and Prim's algorithms (Lessons 17 & 18) repeatedly pull the closest/cheapest frontier node — the heap is what makes them efficient.
• Top-K elements: to find the K largest of n items, keep a min-heap of size K; push each item, and if the heap exceeds K, pop the smallest. O(n log K) time, O(K) space — far better than sorting all n when K is small.
• Merging K sorted lists: a heap of the current front of each list yields the global next element in O(log K) per step — the multi-way merge behind external sorting.
• Median of a stream / scheduling / event simulation: two heaps straddling the median; earliest-deadline-first schedulers; discrete-event simulators ordered by event time.

Worked example: K largest with a size-K min-heap

Find the 3 largest of [4, 1, 7, 3, 8, 5]. Keep a min-heap capped at 3.

Processing: [4, 1, 7, 3, 8, 5]  (K=3)

After 4:   heap = {4}              size=1
After 1:   heap = {1, 4}           size=2
After 7:   heap = {1, 4, 7}        size=3  (full)

After 3:   3 ≤ heap.min (1) → skip          heap = {1, 4, 7}
After 8:   8 > heap.min (1) → push 8, pop 1 heap = {3? ...}

Wait — let's redo with correct K=3 cap logic:
  push(4):   {4}
  push(1):   {1, 4}       (sift-up: 1 < 4 → swap)
  push(7):   {1, 4, 7}    full
  see 3:     3 > min(1)? No 3 > 1 → push, pop min
             push 3 → {1, 3, 4, 7} → pop 1 → {3, 4, 7}
  see 8:     8 > min(3)? Yes → push, pop min
             push 8 → {3, 4, 7, 8} → pop 3 → {4, 7, 8}
  see 5:     5 > min(4)? Yes → push, pop min
             push 5 → {4, 5, 7, 8} → pop 4 → {5, 7, 8}

Final heap: {5, 7, 8} → the 3 largest. ✓
Cost: O(n log K) = O(6 · log 3) ≈ O(10)  vs  O(n log n) = O(6·2.6) ≈ O(16)

Common pitfalls

• Expecting sorted order from a heap. Only the root is guaranteed extreme; the array is *not* sorted. To get sorted output, pop repeatedly (that's heapsort).
• Trying to search a heap. No interior ordering means O(n) search. If you need lookup, pair the heap with a hash map, or use a different structure.
• Building with n inserts instead of heapify. O(n log n) when O(n) is available. Bottom-up sift-down builds in linear time.
• Index arithmetic off by one. 0-based uses 2i+1 / 2i+2 / (i−1)/2; 1-based uses 2i / 2i+1 / i/2. Mixing conventions corrupts the tree — pick one.
• Using a max-heap for top-K largest. A max-heap of all n costs O(n) space and n pops; the size-K *min*-heap is the efficient idiom. Match the heap's polarity to what you evict, not to what you want.

When to use vs avoid

• Use: you repeatedly need the min or max of a changing set; top-K; scheduling by priority; the frontier in graph shortest-path/MST algorithms; k-way merges.
• Avoid: you need full sorted iteration or interior search (use a balanced BST), or you need the extreme *once* on a static array (a single O(n) scan beats building a heap).

Practice problems

1. Median maintenance. Given a stream of integers, maintain the median at all times. Hint: use two heaps — a max-heap of the lower half and a min-heap of the upper half. After each insertion, balance their sizes so they differ by at most 1.
2. K-way merge. You have K sorted arrays. Merge them into a single sorted array in O(N log K) total time, where N is the total number of elements. Hint: push the first element of each array into a min-heap along with its array index; pop the minimum and push the next element from that same array.
3. Heap sort in-place. Given an array, sort it in place using a max-heap. Use O(n) heapify, then repeatedly swap the max (root) to the end and sift-down the shrunken heap. No extra space needed.

Key takeaways

• A heap is a complete tree with the parent-below-children property, stored pointerless in an array via index arithmetic.
• peek is O(1); push and pop are O(log n) via sift-up and sift-down; building from an array is O(n).
• It gives only the extreme element — no sorted order, no interior search — and that restraint is exactly why it's so cheap and cache-friendly.
• The priority queue it implements powers Dijkstra, Prim, top-K, k-way merge, and event scheduling.
• For top-K largest, cap a min-heap at K: O(n log K), O(K) space, no full sort.

Next, back to trees with a specialized twist for strings: the trie, where the path *is* the key. Drill heap operations and top-K patterns in the **AI Learning app**.

AI Learning: AI/ML/DS Q&A

A private, offline app to learn Artificial Intelligence, Machine Learning & Data Science at your own level: ~10,000 Q&A, illustrated guides, cheat sheets, quizzes and mock tests.

Coming soon toGoogle Play