Topics

Heaps: A Study Guide

A heap is a complete binary tree with a simple ordering rule: in a min-heap, every parent is smaller than or equal to its children, so the smallest element is always at the root. (A max-heap flips the comparison.) The heap does not fully sort its elements; it only guarantees the extreme value sits on top, which is exactly what you need for a priority queue.

Why Heaps Matter#

Whenever a problem asks for the “top k”, the “kth largest”, the “next smallest”, or “process the cheapest item next”, a heap is usually the answer. Dijkstra’s shortest-path algorithm, Huffman coding, merge-k-sorted-lists, and median-of-a-stream all lean on heaps. The heap gives you repeated access to the min or max without paying O(n log n) to fully sort.

Key Operations and Their Big-O#

Because a heap is stored as an array and its height is O(log n), the core operations are cheap:

OperationTimeNotes
Peek min/maxO(1)It is the root
Push (insert)O(log n)Bubble up
Pop (extract root)O(log n)Sift down
Build heap from n itemsO(n)Heapify, not n pushes
Search arbitrary valueO(n)Heaps are not for lookup

Note the last row: a heap answers “what is the extreme?” fast but “does value x exist?” slowly. Use a hash set for membership.

A Short Example#

Python’s heapq is a min-heap. For “k largest”, keep a heap of size k and evict the smallest:

1import heapq
2
3def k_largest(nums, k):
4    heap = nums[:k]
5    heapq.heapify(heap)          # O(k)
6    for x in nums[k:]:
7        if x > heap[0]:          # bigger than the smallest kept
8            heapq.heapreplace(heap, x)
9    return heap                  # the k largest, unordered

Common Pitfalls#

  • Wanting a max-heap in Python. heapq is min-only; push -value (or a wrapper) to simulate a max-heap.
  • Building with repeated pushes. heapify is O(n); n individual pushes is O(n log n). Prefer heapify when you have all the data up front.
  • Treating a heap like a sorted list. It is not sorted beyond the root. Popping everything gives you sorted order, but iterating the array does not.
  • Comparing complex items. Pushing tuples works because Python compares element-wise, but a tie on the first element then compares the second, which can raise on non-comparable payloads. Add a tiebreaker index.

Where the Curriculum Covers This#

In the 60-day challenge: