Free lesson · DSA Mastery - Interview Prep, End to End

Introduction to Heaps

Medium7 min readdsaheaps

Introduction to Heaps

The trie section organized data by the characters of a string so that prefix questions became single walks. This section turns to a different organizing principle again - not ordering by full comparison like a BST, not prefix sharing like a trie, but priority. A heap keeps one element - the smallest or the largest - instantly available at all times, and lets you insert new elements and remove that extreme element in O(log n). It does not keep everything sorted; it makes one strong promise (the top is always correct) and pays almost nothing for it. That single promise is the engine behind the recurring "K-something" pattern (K-th largest, top-K frequent, K closest), behind merging many sorted streams, behind scheduling by priority, and - much later - behind Dijkstra-style graph search.

This is the introduction to the section. It defines the heap structure and its array layout, explains the two operations everything builds on (sift-up and sift-down), fixes the conventions used throughout the section, and frames when a heap is the right tool versus sorting or a balanced BST.

The Core Idea: A Weak But Cheap Ordering

A sorted array gives you total order - every element in its exact place - but maintaining that under insertions costs O(n) per insert. A heap gives you far less: only the guarantee that the top element is the minimum (or maximum). In exchange, insertion and removal of the top cost O(log n). For problems that repeatedly ask "what's the smallest/largest right now?" and then remove or replace it, that weak guarantee is exactly enough, and the cheap cost is what makes the algorithm efficient.

Concretely, a binary heap is a complete binary tree (every level full except possibly the last, which fills left to right) obeying the heap property: in a min-heap, every node is <= its children, so the global minimum sits at the root; in a max-heap, every node is >= its children, so the maximum is at the root. Note what the heap property does not say: siblings are unordered, and a node deep in the tree can be smaller than a node in a different branch nearer the root. The order is vertical (parent-to-child) only - that is the "weak" part, and it is why a heap cannot answer "give me the k-th element in sorted order" without removing the first k−1.

graph TD
    A((1)) --> B((3))
    A --> C((2))
    B --> D((7))
    B --> E((4))
    C --> F((5))
    C --> G((6))

    style A fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style D fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style E fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style G fill:#4338ca,stroke:#6366f1,color:#f1f5f9

This diagram shows a min-heap. The root holds the minimum value one, highlighted in green. Every parent is less than or equal to its children, but siblings and cross-branch nodes are not ordered relative to each other, so three and two sit above larger values without any left-to-right ordering.

The Array Layout - No Pointers Needed

A heap is almost never stored with node objects and pointers. Because it is a complete tree, it maps perfectly onto a flat array with a simple index arithmetic, which is compact and cache-friendly:

• The root is at index 0.
• For a node at index i: its left child is at 2*i + 1, its right child at 2*i + 2, and its parent at (i - 1) / 2 (integer division).

So the tree above is just the array [1, 3, 2, 7, 4, 5, 6]. Walking from a node to its parent or children is pure arithmetic - no traversal, no allocation. This index trick is one of the most elegant in all of data structures: the tree shape is implicit in the array positions.

int parent(int i) { return (i - 1) / 2; }
int left(int i)   { return 2 * i + 1; }
int right(int i)  { return 2 * i + 2; }

Note: The completeness of the tree is what makes the array layout work without gaps. Because the last level fills left to right with no holes, the elements pack contiguously into the array, and the index formulas always land on real positions (bounded by the array size). A non-complete tree would leave gaps and break the arithmetic.

The Two Operations Everything Builds On

Every heap operation is built from two "repair" routines that restore the heap property after a local violation. Both walk a single root-to-leaf or leaf-to-root path, so both are O(log n).

Sift-up (bubble-up): used after inserting at the end of the array. The new element may be smaller than its parent (in a min-heap), violating the property. Swap it upward with its parent repeatedly until it is >= its parent or reaches the root.

Sift-down (bubble-down): used after removing the root. You move the last element to the root (filling the hole), then it may be larger than its children. Swap it downward with its smaller child repeatedly until it is <= both children or reaches a leaf.

graph TD
    A["insert x: append at end"] --> B["sift-up: while x < parent, swap up"]
    B --> C["heap property restored, O(log n)"]
    D["extract-min: save root as answer"] --> E["move last element to root, shrink"]
    E --> F["sift-down: while node > smaller child, swap down"]
    F --> G["heap property restored, O(log n)"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style E fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style G fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the two heap repair operations. Insert appends an element and sifts it up past larger parents; extract-min removes the root, moves the last element to the top, and sifts it down past smaller children, each restoring the heap property in logarithmic time.

From these two primitives come the standard operations: peek (read the root, O(1)), push/insert (append + sift-up, O(log n)), pop/extract (remove root + sift-down, O(log n)), and heapify (build a heap from an unsorted array in O(n) by sifting down every internal node from the bottom up - notably better than n inserts).

You Will Use the Library, Not Build It

In interviews and in this section, you almost never implement the array and sift routines by hand - you use the language's built-in priority queue. The mechanics above matter for understanding (and occasionally for a follow-up question), but the code uses the library:

// Java: PriorityQueue is a MIN-heap by default
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

minHeap.offer(5); minHeap.offer(1); minHeap.offer(3);
int smallest = minHeap.peek();   // 1, O(1)
minHeap.poll();                  // removes 1, O(log n)

// Custom priority via comparator (e.g., by a field or computed key)
PriorityQueue<int[]> bySecond = new PriorityQueue<>((a, b) -> a[1] - b[1]);

Important: Java's PriorityQueue is a min-heap by default - peek/poll give the smallest element. For a max-heap, pass Collections.reverseOrder() or a reversed comparator. Getting this backwards is the single most common heap bug: half the "my answer is inverted" problems are a min-heap used where a max-heap was needed. Throughout this section, we state explicitly which orientation each problem needs and why.

When a Heap Is the Right Tool

The heap's niche is precise. Reach for it when:

• You repeatedly need the min or max of a changing collection - elements arrive and/or the extreme is removed over time. (If the collection is fixed and you need the extreme once, a single linear scan beats building a heap.)
• You need the K smallest/largest of a large or streaming set without sorting everything - a heap of size K gives O(n log K), beating O(n log n) full sort, and works on streams where you never hold all n at once.
• You are merging multiple sorted sequences - a heap of the current front of each sequence always yields the next overall element.
• You need priority-ordered processing - scheduling, event simulation, Dijkstra/Prim later - where you always handle the highest-priority item next.

Tip: The strongest signal for a heap is the phrase "K-th largest / smallest", "top K", "K closest", "K most frequent", or any setting where elements stream in and you must keep the best few. The second strongest is "merge K sorted ...". If you see "median of a stream", think two heaps. We will name each of these patterns as it appears.

What This Section Covers

The section moves from the structure to its four signature patterns:

• Standard heap problems - direct uses where a heap repeatedly serves the min or max: simulations, greedy choices, and cost-minimization where you always take the cheapest/most-expensive option next.
• Two heaps - a min-heap and a max-heap balanced against each other to track the median of a stream, or to pair a running extreme with a threshold (IPO, sliding-window median).
• K-way merge - a heap holding the front of each of several sorted sequences, producing a merged order one element at a time (merge K lists, k-th smallest in a sorted matrix, smallest range covering K lists).
• Top K elements - the canonical pattern: a size-K heap that retains the K best of a large or streaming set (k-th largest in a stream, top-K frequent, K closest to origin).

Throughout, the recurring decision is which extreme to keep cheap and how big to let the heap grow. A subtle but high-leverage trick recurs: to keep the K largest, use a min-heap of size K (so the easiest to evict - the smallest of your current best - is at the top); to keep the K smallest, use a max-heap of size K. That inversion is the heart of the Top K pattern, and we build up to it deliberately.

The next topic, Last Stone Weight, is the simplest possible heap simulation: repeatedly take the two heaviest stones, smash them together, and put back the difference, until one or none remains. A max-heap makes "the two heaviest" an O(log n) operation per round, turning a problem that would otherwise need repeated re-sorting into a clean loop of pop-pop-push. It is the gentlest possible first use of the structure - establishing the push/poll rhythm and the max-heap orientation before the greedy and pattern problems that follow.

Back to DSA Mastery - Interview Prep, End to End