Heap Fundamentals

Heaps are one of the most practical data structures in interviews and real systems. They power priority queues, schedulers, [Top K Problems](/blog/algorithms/heap-top-k/top-k-problems), [Dijkstra](/blog/algorithms/bfs-graph-traversal/dijkstra), and much more.

If you see a problem where you repeatedly need to pick the smallest / largest element among many candidates that are also changing over time, a heap (priority queue) should be one of your first instincts.

What Is a Heap?

A (binary) heap is a complete binary tree stored in an array with an ordering constraint:

• Min‑heap: every node is ≤ its children ⇒ the minimum is always at the root.
• Max‑heap: every node is ≥ its children ⇒ the maximum is always at the root.

Key properties:

• Shape property: the tree is complete – filled level by level from left to right.
• Heap property: each node obeys the min/max ordering with respect to its children.

Because the tree is complete, we can store it compactly in an array:

• Parent index: i
• Left child index: 2 * i + 1
• Right child index: 2 * i + 2

No explicit pointers are needed, which makes heaps both simple and cache‑friendly.

Core Operations and Complexity

For a binary heap storing n elements:

Operation	Description	Time
insert(x)	Push a new element	O(log n)
getMin / getMax	Peek top element	O(1)
extractMin / extractMax	Pop top element	O(log n)
buildHeap	Heapify from an arbitrary array	O(n)

Two fundamental internal operations:

• sift up (bubble up) – used in insert
• sift down (heapify) – used in extract and buildHeap

How Insert and Extract Work

Insert (push)

1. Append the new element at the end of the array (bottom‑right position in the tree).
2. While the heap property is violated with the parent, swap up:
   • Min‑heap: while a[parent(i)] > a[i], swap and move i = parent(i).
3. Stop when the property is satisfied or we reach the root.

Height of a complete binary tree is O(log n), so insertion is O(log n).

Extract Top (pop)

1. Save the root element as the answer.
2. Move the last element in the array to the root position, and decrease heap size by 1.
3. Starting from the root, repeatedly compare with its children and swap down with the smaller (or larger) child until the heap property is restored.

Again the height is O(log n), so extraction is O(log n).

Heap vs Array vs Balanced Tree

Heaps sit between arrays and balanced trees:

Structure	Best at	Top access	Insert / Delete	Search by key
Sorted array	Global order / binary search	O(1)	O(n)	O(log n)
Binary heap	Repeated min / max	O(1)	O(log n)	O(n)
Balanced BST	Order + flexible search by key	O(1) (min/max)	O(log n)	O(log n)

In most interview problems where you just need “always pick current best element” and don’t do arbitrary searches by key, a heap is the simplest and most efficient choice.

Typical Interview Use Cases

You will see heaps over and over in these patterns:

• [Top K Problems](/blog/algorithms/heap-top-k/top-k-problems)
  • Keep a heap of size k and discard worse candidates.
  • E.g. “find top K frequent elements”, “K closest points to origin”.
• [Streaming Scenarios](/blog/algorithms/heap-top-k/streaming-scenarios)
  • Data arrives online, but you only need the best/smallest K so far.
  • Heaps give O(log k) update per new element.
• Shortest path / graph algorithms
  • [Dijkstra](/blog/algorithms/bfs-graph-traversal/dijkstra) uses a min‑heap to always pick the node with the smallest tentative distance.
• Scheduling / load balancing
  • Assign jobs to machines based on current load (min‑heap on machine load).

If you repeatedly say “pick current minimum/maximum” inside a loop and the candidate set changes, you should almost certainly think heap.

Example: Top K Smallest Elements

One of the most classic heap interview questions:

Given an array of integers and an integer k, return the k smallest elements in any order.

Idea

• Use a max‑heap of size k:
  • First push the first k elements.
  • For each remaining element x:
    • If x is smaller than the current maximum in the heap, pop the max and insert x.
  • The heap finally contains the k smallest elements seen so far.

Time complexity: O(n log k), space O(k).

Java sketch

JavaCopy
import java.util.*;

public List<Integer> kSmallest(int[] nums, int k) {
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
    for (int x : nums) {
        if (maxHeap.size() < k) {
            maxHeap.offer(x);
        } else if (x < maxHeap.peek()) {
            maxHeap.poll();
            maxHeap.offer(x);
        }
    }
    return new ArrayList<>(maxHeap);
}

Common Pitfalls and Gotchas

Some frequent mistakes in heap problems:

• Using the wrong heap type
  • For top‑K largest elements, you usually want a min‑heap of size K.
  • For top‑K smallest elements, a max‑heap of size K is natural.
• Forgetting to limit heap size
  • If you don’t cap the heap at k, complexity becomes O(n log n) instead of O(n log k).
• Confusing 0‑based and 1‑based indexing
  • In a hand‑rolled heap, be consistent with parent/child index formulas.
• Incorrect comparator
  • In Java / C++ it’s easy to accidentally reverse the comparator and get the wrong order.

In interviews, always state clearly:

• Which variant you’re using (min‑heap / max‑heap).
• What’s stored in the heap (raw values, pairs, custom objects).
• What the comparator is (e.g. first by distance, then by name).

When to Reach for a Heap

As a quick recognition checklist:

1. Do you need to repeatedly get the current best (min or max) element?
2. Is the candidate set changing dynamically (elements added/removed over time)?
3. Do you only care about a small subset, like top K or bottom K?

If the answer is “yes” to most of these, a heap (priority queue) is almost always a good choice.

Recommended Follow‑Up Topics

After Heap Fundamentals, natural follow‑ups include:

• [Top K Problems](/blog/algorithms/heap-top-k/top-k-problems) (Fixed‑size heap patterns)
• [Streaming Scenarios](/blog/algorithms/heap-top-k/streaming-scenarios) and Online Algorithms
• Heaps in Graph Algorithms: [Dijkstra](/blog/algorithms/bfs-graph-traversal/dijkstra), [Prim's Algorithm](/blog/algorithms/minimum-spanning-tree/prim)
• Indexed / keyed heaps (decrease‑key operations)
• Comparison with specialized structures (Fibonacci heap, pairing heap – mostly theory)

This progression pairs nicely with a “Heap / Top K” section in an algorithms interview prep series.