Heaps

Why This Matters

Heaps answer "what is the best next item?" without sorting everything. That question appears in schedulers, top-k retrieval, event simulation, Dijkstra's algorithm, A*, streaming leaderboards, and beam search.

The key abstraction is the priority queue: insert items with priorities and repeatedly remove the highest or lowest priority item.

Learning Objectives

By the end, you should be able to:

• State the heap invariant for min-heaps and max-heaps.
• Explain the array layout of a complete binary heap.
• Analyze push, peek, pop, buildHeap, and top-k selection.
• Use a heap when the repeated operation is "choose the best next item."
• Distinguish a heap, a sorted array, a binary search tree, and a priority queue abstraction.

Core Idea

In a min-heap, every parent key is no larger than its children. The smallest item sits at the root. A binary heap stores that tree in an array.

For zero-based arrays, parent and child positions are:

parent(i) = floor((i - 1) / 2)
left(i)   = 2i + 1
right(i)  = 2i + 2

Non-Example or Failure Mode

A heap is not a sorted array. The root is the minimum or maximum, but siblings and cousins do not have a total sorted order. If you repeatedly scan a heap array expecting sorted output, the result is wrong.

The failure mode in production is over-sorting. If you only need the top k items from a large stream, sorting everything pays O(n log n) when a size-k heap can often do the job in O(n log k) time and O(k) memory.

Worked Example

Find the ten largest numbers in a stream. Keep a min-heap of size ten.

for each x in stream:
  if heap has fewer than 10 items:
    insert x
  else if x > heap.min:
    extract min
    insert x
return heap contents

The heap root is always the current tenth-best value. You avoid sorting the entire stream and use only O(k) memory for top-k.

Builder Connections

• Ranking pipelines use heaps for top-k candidate selection.
• Graph shortest-path algorithms use priority queues to select the next frontier node.
• Schedulers use priorities to choose which job runs next.
• LLM decoding can use heaps or partial selection for top-k token filtering.
• Event simulations use heaps to process the next event by timestamp.

Common Mistakes

Diagnostic Questions

Exercises

Beginner:

• Draw the heap after inserting 4, 1, 7, 3.
• Give the array indices for the parent and children of index 5.
• Explain why find-min is constant time.

Intermediate:

• Perform extract-min by hand on a small heap.
• Use a size-3 heap to track top scores in a stream.

Challenge:

• Implement a priority queue and use it in Dijkstra's algorithm on a weighted graph.

Diagram Recommendation

Type: heap-tree to array mapping.

Caption: "A complete binary tree laid out level by level in an array."

Purpose: Show why heaps need no explicit child pointers and why parent-child index arithmetic works.

Implementation Task

Implement a min-heap with push, peek, and pop.

class MinHeap {
  private items: number[] = [];

  push(value: number) {
    this.items.push(value);
    this.bubbleUp(this.items.length - 1);
  }

  peek() {
    return this.items[0];
  }

  private bubbleUp(index: number) {
    while (index > 0) {
      const parent = Math.floor((index - 1) / 2);
      if (this.items[parent]! <= this.items[index]!) break;
      [this.items[parent], this.items[index]] = [
        this.items[index]!,
        this.items[parent]!,
      ];
      index = parent;
    }
  }
}

Finish pop with bubble-down, then test it with random arrays against sorted output.

Next Topics

• Sorting
• Graphs
• Greedy algorithms

References

• Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (4th ed., 2022). Ch. 6.
• MIT OpenCourseWare. 6.006 Introduction to Algorithms, Spring 2020.
• Sedgewick and Wayne. Algorithms (4th ed., 2011). Ch. 2.
• Skiena. The Algorithm Design Manual (3rd ed., 2020). Ch. 3.