What Is a Heap?
A heap is a complete binary tree stored in a flat array. "Complete" means every level is fully filled except possibly the last, which fills left to right. Two flavours:
- Min heap: every parent is less than or equal to its children. The smallest element sits at the root.
- Max heap: every parent is greater than or equal to its children. The largest element sits at the root.
Whenever you need quick access to the smallest (or largest) item in a changing collection, a heap is the go-to structure. Operating systems use heaps for CPU scheduling, graph algorithms use them for shortest paths, and interviewers love them for "Top K" and "Kth largest" problems.
Dual representation: tree and array
A heap is conceptually a tree but physically an array. For a node at index i:
- Left child:
2*i + 1 - Right child:
2*i + 2 - Parent:
(i - 1) // 2
Min Heap — Tree View + Array View
Parent ≤ children at every node
Index 0 is the root (smallest). Left child of i = 2i+1, right = 2i+2.
Heap Operations & Complexity
Understanding heap operations is essential for interviews. Here's what each one costs and why:
Core operations
- Insert (push) — O(log n): Add the new element at the end of the array, then "bubble up" (swap with parent) until the heap property is restored. The tree has log n levels, so at most log n swaps.
- Extract min/max — O(log n): Remove the root, move the last element to the root, then "bubble down" (swap with the smaller child) until the heap property is restored. Again, at most log n swaps.
- Peek — O(1): The root is always at index 0. Just read it.
- Heapify — O(n): Convert an arbitrary array into a heap. Start from the last non-leaf node and bubble down each one. Despite having n/2 nodes to process, the math works out to O(n) total — not O(n log n).
Python's heapq Module
Python's standard library provides heapq — a min heap implementation that operates on a plain list. No special class needed.
Essential functions
heapq.heappush(heap, val)— push a value, maintain heap orderheapq.heappop(heap)— pop and return the smallest valueheapq.heapify(list)— convert a list into a heap in-place, O(n)heapq.nlargest(k, iterable)— return the k largest elementsheapq.nsmallest(k, iterable)— return the k smallest elementsheapq.heapreplace(heap, val)— pop smallest, push val (faster than pop + push)
Max heap trick: negate values
Python's heapq is min-heap only. To simulate a max heap, negate values on the way in and negate again on the way out:
Problem: Kth Largest Element
Given an unsorted array and an integer k, find the kth largest element. This is LeetCode 215 and a staple at Google, Amazon, and Meta interviews.
Approach 1: heapq.nlargest — simple
One line with heapq.nlargest(k, nums)[-1]. Internally it builds a heap of size k, so it's O(n log k).
Approach 2: min-heap of size k — optimal
Maintain a min-heap of the k largest elements seen so far. For each new number, if it's larger than the smallest in the heap, replace it. At the end, the root is the kth largest.
Problem: Top K Frequent Elements
Given an integer array and k, return the k most frequent elements. This is LeetCode 347 — another Amazon and Meta favourite.
Strategy: Count frequencies with a Counter, then use a heap to extract the top k.
[1, 2] and [2, 1] are correct. Interviewers care about the algorithm, not the output order.
Problem: Merge K Sorted Lists
Given k sorted lists, merge them into one sorted list. This is LeetCode 23 — a hard problem that becomes elegant with a heap.
Strategy: Push the first element of each list onto a min-heap (along with the list index and element index). Pop the smallest, add it to the result, then push the next element from that same list.
Heap Sort — The Concept
Heap sort is a comparison-based sorting algorithm that uses a heap. Two steps:
- Build a heap from the input array — O(n)
- Extract the min (or max) repeatedly and collect results — n extractions at O(log n) each = O(n log n)
Total: O(n log n) time, and if done in-place with a max heap, O(1) extra space.
Try It Yourself
Find the Kth Largest Element
Use heapq to find the kth largest element in an array. Try both approaches: nlargest and the min-heap of size k.
Challenge
Design a class MedianFinder that supports two operations:
add_num(num)— add a number to the data streamfind_median()— return the median of all numbers added so far
Hint: Use two heaps — a max heap for the lower half and a min heap for the upper half. Keep them balanced so their sizes differ by at most 1.
Example: add 1, 2, 3 → medians are 1.0, 1.5, 2.0
Complexity target: O(log n) per add, O(1) per find_median.
len(max_heap) == len(min_heap) or len(max_heap) == len(min_heap) + 1. The median is either the top of max_heap (odd count) or the average of both tops (even count). This is LeetCode 295 — "Find Median from Data Stream."Quiz
heapq.heapify()?heapq?You've conquered heaps and priority queues.
Now master the full interview toolkit.
Join the Best AI Programs — three 5-month courses, fully online, with placement assistance. Week 1 is free.
Explore our AI-era courses →