What is a Heap?
Data Structures·7 min read·code in python
A heap is a complete binary tree that satisfies the heap property: in a min-heap every parent is smaller than or equal to its children, so the minimum sits at the root (a max-heap flips this). Stored compactly in an array, it powers priority queues with O(log n) insert and extract.
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.
The code
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 topRun it in the browser IDE, free on the platform. Open the IDE
Complexity
| Time | Insert O(log n), extract-min/max O(log n), peek O(1), build-heap (heapify) O(n), heap sort O(n log n). |
|---|---|
| Space | O(n) for the backing array; O(1) extra for operations, and heap sort runs in place. |
Insert 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.
Watch it run
Reading the steps is one thing. Watching it move on your own input, one step at a time, is where the picture sticks.
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.
Heap: questions we get
Is a heap the same as a binary search tree?
No. Both are binary trees, but a BST keeps a full left-to-right ordering that makes searching any value fast, while a heap only guarantees the root is the minimum or maximum and leaves siblings unordered. A heap trades searchability for cheap O(log n) insert and extract of the extreme element.
What is the time complexity of heap operations?
Insert and extract-min/max are O(log n) because each follows a single root-to-leaf path. Peeking at the top is O(1). Building a heap from n items with the standard heapify is O(n), and heap sort runs in O(n log n).
When should I use a heap instead of sorting?
Use a heap when items arrive over time or when you only need the extreme (or the top k), not a full ordering. Sorting is a one-time O(n log n) on static data; a heap gives O(log n) insert/extract as data changes and solves top-k in O(n log k), which beats sorting everything when k is small.
Is a heap hard to learn?
The concept is friendly, 'a parent beats its children' is the entire rule. The tricky parts are the array index math and the sift-up/sift-down logic, which are far easier once you watch the swaps happen step by step. Most people are comfortable after implementing push and pop by hand once.
Related concepts
Reading is the easy part. In a batch you build it, say it out loud in a scored mock round and hear what an interviewer would think.
Talk to mentor