VisaSpark
Sign in
intermediate21 min

Heaps and Priority Queues

The array-backed tree that always gives you the smallest (or largest) element in O(1), and how it stays that way in O(log n) per update.

What you'll learn

  • Explain the heap ordering property and how it differs from a BST's ordering invariant
  • Implement a min-heap's insert and extract-min operations
  • Explain why a priority queue is the right structure for 'always process the most urgent item next'

Prerequisites

Explanation

A min-heap is a binary tree with a weaker, cheaper-to-maintain rule than a BST: every parent is less than or equal to both its children — unlike a BST, there's no ordering requirement between siblings or across subtrees, only along each parent-child edge. That relaxed rule is precisely why a heap doesn't need BST-style rebalancing to stay efficient: a heap is additionally always kept complete (every level fully filled, except possibly the last, which fills left to right with no gaps), a shape constraint strong enough to guarantee O(log n) height on its own, with no separate balancing step required.

Because a heap is always complete, it can be stored directly in a plain array, with no explicit node/pointer objects at all: for a node at index i, its children live at indices 2i + 1 and 2i + 2, and its parent lives at index Math.floor((i - 1) / 2) — pure arithmetic, no traversal needed to find a relative. This is a genuinely different, more compact representation than every tree structure covered so far in this course.

The two core operations are insert (add the new value at the end of the array, then repeatedly swap it with its parent — "bubble up" — as long as it's smaller than that parent, restoring the heap property in O(log n), proportional to the tree's height) and extract-min (the minimum is always the root, index 0 — remove it, move the last array element into the now-empty root position, then repeatedly swap it with its smaller child — "bubble down" — until the heap property holds again, also O(log n)). Reading the minimum without removing it (peek) is O(1), since it's always sitting at index 0 — this combination (instant access to the smallest element, logarithmic update) is exactly what makes a heap the standard implementation behind a priority queue: a queue where "next" doesn't mean "oldest," it means "highest priority" (lowest value, for a min-heap), which is the structure behind task schedulers, and — in a later lesson — Dijkstra-style shortest-path algorithms that always need to process the currently-closest unvisited node next.

Example

A min-heap backed by a plain array, with insert (bubble up) and extractMin (bubble down).

function insert(heap, value) {
  heap.push(value);
  let i = heap.length - 1;
  while (i > 0) {
    const parent = Math.floor((i - 1) / 2);
    if (heap[parent] <= heap[i]) break; // heap property already holds
    [heap[parent], heap[i]] = [heap[i], heap[parent]]; // swap up
    i = parent;
  }
}

function extractMin(heap) {
  if (heap.length === 0) throw new Error("heap is empty");
  const min = heap[0];
  const last = heap.pop();
  if (heap.length > 0) {
    heap[0] = last;
    let i = 0;
    while (true) {
      const left = 2 * i + 1, right = 2 * i + 2;
      let smallest = i;
      if (left < heap.length && heap[left] < heap[smallest]) smallest = left;
      if (right < heap.length && heap[right] < heap[smallest]) smallest = right;
      if (smallest === i) break;
      [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
      i = smallest;
    }
  }
  return min;
}

const heap = [];
for (const v of [5, 2, 8, 1, 9]) insert(heap, v);
console.log(extractMin(heap)); // 1 -- the current minimum, in O(log n)
console.log(extractMin(heap)); // 2 -- the next minimum

Try it yourself

Insert the values [10, 4, 15, 2] one at a time and print the heap array after each insertion to see it stay valid.

Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.

Loading editor…

Guided exercise

Guided exercise

Write parentIndex(i), leftChildIndex(i), rightChildIndex(i) -- the three pure arithmetic functions that locate relatives in an array-backed heap, with no traversal.

Checks: computes the correct parent index for both children of the root · computes the correct child indices for the root · parentIndex correctly inverts leftChildIndex

Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.

Loading editor…

Stuck? Get a hint.

Independent exercise

Independent exercise

Write isValidMinHeap(heap) that checks whether an array satisfies the min-heap property EVERYWHERE (every parent <= both its children, for every node that has children) -- not just at the root.

Checks: accepts a genuinely valid min-heap array · rejects an array violating the heap property at some parent/child pair · an empty array is trivially valid · a single-element array is trivially valid

Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.

Loading editor…

Stuck? Get a hint.

Common mistakes

  • Confusing a heap's ordering property with a BST's -- a heap only guarantees parent <= children, with NO relationship between siblings or across subtrees; you cannot do a BST-style search in a heap.
  • Forgetting that extractMin must move the LAST element to the root before bubbling down -- simply removing the root and promoting one of its children directly breaks the heap's completeness property.
  • Assuming a heap's array representation is sorted -- it is not; only the root (index 0) is guaranteed to be the minimum. heap[1] is not necessarily smaller than heap[2] in any fixed relationship beyond both being >= heap[0].

Knowledge check

Knowledge check

1. How does a min-heap's ordering property differ from a BST's ordering invariant?
2. Why can a complete binary tree (like a heap) be stored in a plain array with no explicit pointers?
3. What is the time complexity of peek() (reading, not removing, the minimum) on a min-heap?

Takeaway

A heap trades a BST's strong, whole-subtree ordering for a weaker, purely local parent-child rule plus a completeness guarantee — that combination is what lets it live in a plain array with O(1) peek and O(log n) insert/extract, making it the standard backing structure for a priority queue.

Summary

A min-heap requires every parent <= its children, and stays complete, which lets it be stored in an array using pure index arithmetic for parent/child relationships. insert bubbles a new value up; extractMin removes the root, promotes the last element, and bubbles it down. Both are O(log n); peek is O(1).

References

Your notes

Notes save automatically.

Finished this lesson?

Mark it complete to track your progress and schedule a future review.

Next: Recursion and Divide-and-Conquer →