Heaps
15 min
A heap is a tree-shaped structure that keeps one guarantee: the smallest element (min-heap) is always at the root, retrievable in O(1) — push and pop are both O(log n). That makes it the standard structure for a priority queue: "give me the next most-urgent item," repeatedly, efficiently.
Python's heapq module turns a plain list into a min-heap in place:
import heapq
nums = [5, 3, 8, 1, 9]
heapq.heapify(nums) # O(n) — reorders in place
heapq.heappush(nums, 0) # O(log n)
heapq.heappop(nums) # 0 — O(log n), always removes the smallest
heapq.nsmallest/nlargest are the shortcut you'll actually reach for in real code — they're O(n log k), better than a full O(n log n) sort when k is small.
A classic heap use case: merging several sorted lists into one sorted
list, without concatenating and re-sorting everything. Keep a heap of
(value, which_list, index) — one entry per list's current head. Pop the
smallest, append it to the result, then push that list's next element.
Total cost is O(n log k) for n total elements across k lists, versus
O(n log n) for sort-everything-together.
Write a function `k_smallest(nums, k)` that returns the k smallest values in `nums`, sorted ascending. Use `heapq`.
Write a function `merge_sorted_lists(lists)` that merges a list of already-sorted lists into one sorted list, using a heap to always pick the smallest available head element (a k-way merge).
What is the time complexity of pushing or popping a single element from a `heapq`-based heap of size n?
You can use heapq for priority-queue-style problems and implement a k-way merge with a heap.