The idea: keep the extreme on top
Picture a hospital ER where patients are seen by urgency, not by arrival order. New patients keep coming, and at every moment you only need the single most urgent case. Re-sorting the whole room each time would be wasteful. A heap is the data structure built for exactly this: it keeps the extreme element — the smallest or the largest — instantly reachable while staying cheap to update.
A heap is shaped like a binary tree, but a loose one. Its only rule is the heap property: a parent is always more extreme than its children — smaller in a min-heap, larger in a max-heap. This is deliberately weaker than a binary search tree: siblings are unordered and the tree is not sorted left to right. That looseness is the whole point. It lets the heap repair itself after any change by touching just one path from root to leaf.
How it works: an array and two sift operations
A heap is complete — every level is full except possibly the last, which fills left to right. That completeness means you can drop pointers entirely and store the tree in a plain array. For a node at index i, its children live at 2i+1 and 2i+2 and its parent at (i-1)//2. The root — your minimum or maximum — is always index 0.
Two operations maintain the property. Insert appends to the end, then sifts up: swap with the parent while the order is violated. Extract removes index 0, moves the last element into its place, then sifts down: swap with the smaller (or larger) child until order is restored. Each path is at most the tree's height, log n, so insert and extract are both O(log n), while peeking at the top is O(1). Watching those swaps animate makes the whole thing click fast.
Heapify and heap sort
Building a heap from an existing array can be done in O(n) — faster than inserting n items one at a time, which is O(n log n) — by sifting down from the last parent up to the root. It is a classic result worth remembering because interviewers love to test it.
Heap sort builds on this: construct a max-heap, then repeatedly extract the maximum and place it at the end of the array. That gives O(n log n) sorting in O(1) extra space, since the heap and the sorted region share one array. It is not the fastest sort in practice, but it is the textbook example of a heap earning its keep.
class MinHeap:
def __init__(self):
self.data = []
def push(self, x):
self.data.append(x)
i = len(self.data) - 1
while i > 0 and self.data[(i - 1) // 2] > self.data[i]:
p = (i - 1) // 2
self.data[i], self.data[p] = self.data[p], self.data[i]
i = p
def pop(self): # remove and return the minimum
top, last = self.data[0], self.data.pop()
if self.data:
self.data[0] = last
i, n = 0, len(self.data)
while True:
s, l, r = i, 2 * i + 1, 2 * i + 2
if l < n and self.data[l] < self.data[s]: s = l
if r < n and self.data[r] < self.data[s]: s = r
if s == i: break
self.data[i], self.data[s] = self.data[s], self.data[i]
i = s
return topInsert and extract are O(log n) in both the average and worst case; peek is always O(1). Building a heap by repeated sift-down is O(n), not O(n log n) — a common surprise.
When to use it
- You repeatedly need the smallest or largest item from a changing set — a priority queue for task scheduling, event simulation, or the frontier in Dijkstra and A*.
- Top-k problems: keep a size-k heap to find the k largest, k smallest, or k most frequent elements in O(n log k) instead of sorting everything.
- Merging k sorted lists or streams by always pulling the next-smallest head, as in external merge sort.
- Maintaining a running median with two heaps, or any 'get the current extreme fast' need where a full sort is overkill.
Watch out for
- Treating a heap as sorted. It only guarantees the root is extreme — iterating the array is not sorted order, and there is no fast search for an arbitrary value or in-order traversal like a BST.
- In Python, forgetting that heapq is min-only. To get a max-heap you push negated values (or tuples with a negated key) and negate again on the way out.
- Using the wrong heap for top-k. To find the k largest, a size-k min-heap that evicts its smallest is O(n log k) — leaner than heaping all n elements. People instinctively reach for a max-heap and pay more.
Heaps are interview staples, usually in disguise. A prompt rarely says 'use a heap' — it says 'k most frequent elements,' 'merge k sorted lists,' 'find the median from a data stream,' or 'kth largest element.' Recognizing the signal 'I need the current min or max repeatedly' is half the battle. Interviewers look for whether you reach for the built-in priority queue (heapq, PriorityQueue) instead of re-sorting each step, whether you can justify the O(n log k) versus O(n log n) trade-off for top-k, and whether you can state the heap property and explain why insert and extract are O(log n). Knowing that build-heap is O(n) and being able to sketch the two-heaps median pattern are strong bonus signals.