DSA · Chapter 18 of 40
Heaps and Priority Queues
A binary heap is a complete binary tree stored in an array where every parent is smaller (min-heap) or larger (max-heap) than its children. It gives O(log n) insert and remove-top, with O(1) peek at the best element.
A priority queue is the abstract idea; a heap is the usual implementation. It powers scheduling, Dijkstra's algorithm and top-k problems.
Array layout
For index i the children are 2i+1 and 2i+2 and the parent is (i-1)//2, so no pointers are needed.
Top-k pattern
To find the k largest items, keep a min-heap of size k: push each item and pop the smallest whenever the heap exceeds k. Total O(n log k).
Example 1 (python)
import heapq
h = []
heapq.heappush(h, 5)
heapq.heappush(h, 1)
heapq.heappush(h, 3)
print(heapq.heappop(h))
print(h[0])Output
1
3heapq is a min-heap; the smallest element is always at index 0.
Example 2 (python)
import heapq
def top_k(nums, k):
h = []
for n in nums:
heapq.heappush(h, n)
if len(h) > k:
heapq.heappop(h)
return sorted(h, reverse=True)
print(top_k([4, 1, 9, 7, 3], 2))Output
[9, 7]A size-k min-heap solves top-k in O(n log k).
Key points
- Insert and remove-top are O(log n); peek is O(1).
- Heaps are stored as arrays, not with pointers.
- Python heapq is a min-heap — push negatives for a max-heap.
- Top-k and median problems use heaps.
💡 Note: Building a heap from n items with heapify is O(n), not O(n log n).