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.
🏔️
Why heaps matter
Priority queues, task schedulers, Dijkstra's algorithm

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

Tree representation
1
3
5
4
8
9
7

Parent ≤ children at every node

Array representation
1
3
5
4
8
9
7
0
1
2
3
4
5
6

Index 0 is the root (smallest). Left child of i = 2i+1, right = 2i+2.

Key insight:
A heap is NOT fully sorted. It only guarantees the root is the min (or max). Siblings have no ordering between them. That's what makes it faster than a sorted array for repeated insert + extract operations.

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).
Why is heapify O(n) and not O(n log n)?
Most nodes are near the bottom of the tree and only need to bubble down a few levels. Half the nodes are leaves (0 swaps), a quarter need at most 1 swap, an eighth need at most 2 swaps, and so on. The total work sums to O(n), not O(n log n). This is a common interview follow-up question.

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 order
  • heapq.heappop(heap) — pop and return the smallest value
  • heapq.heapify(list) — convert a list into a heap in-place, O(n)
  • heapq.nlargest(k, iterable) — return the k largest elements
  • heapq.nsmallest(k, iterable) — return the k smallest elements
  • heapq.heapreplace(heap, val) — pop smallest, push val (faster than pop + push)
heapq_basics.py Min heap with Python heapq
Output
Heap: [1, 1, 4, 3, 5, 9] 1 Peek: 1 3 largest: [9, 5, 4] 3 smallest: [1, 2, 4]

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:

max_heap_trick.py Simulating a max heap
Output
Largest: 9 Current max: 5
Interview tip:
Mention the negation trick when the interviewer asks about max heaps in Python. It shows you know the standard library's limitations and how to work around them.

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.

kth_largest.py O(n log k) time, O(k) space
Output
2nd largest (nlargest): 5 2nd largest (heap): 5 4th largest: 4
Why min-heap for "kth largest"?
It sounds backwards, but a min-heap of size k naturally evicts the smallest of the k largest seen so far. After processing all elements, the heap's root is exactly the kth largest. Time is O(n log k) vs. O(n log n) for full sorting.

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.

top_k_frequent.py O(n log k) with Counter + heap
Output
Top 2 frequent: [1, 2] Top 2 (heap): [2, 1] Top 2 frequent: [2, 4]
Order may vary:
The problem says "return in any order," so both [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.

merge_k_sorted.py O(N log k) where N = total elements
Output
[1, 2, 3, 4, 5, 6, 7, 8, 9] [0, 1, 2, 3, 4, 5, 6, 7, 8]
Why O(N log k)?
The heap never holds more than k elements (one per list). Each of the N total elements is pushed and popped once, costing O(log k) each. Compare this to the naive approach of merging lists one by one, which is O(Nk).

Heap Sort — The Concept

Heap sort is a comparison-based sorting algorithm that uses a heap. Two steps:

  1. Build a heap from the input array — O(n)
  2. 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.

heap_sort.py O(n log n) using heapq
Output
Sorted: [1, 2, 3, 4, 5, 6, 7, 8, 9] Sorted: [8, 15, 31, 42, 56, 73]
Interview context:
You'll rarely be asked to implement heap sort from scratch. But you should know the idea: "build heap, extract repeatedly." More commonly, interviewers ask about heap sort's time complexity (O(n log n) always — no worst case degradation like quicksort) and space (O(1) if done in-place).

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

Find the median from a data stream
Your task:

Design a class MedianFinder that supports two operations:

  • add_num(num) — add a number to the data stream
  • find_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.

Use a max heap (negate values) for the smaller half and a min heap for the larger half. After each insertion, rebalance so 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

Question 1 of 5
What property defines a min heap?
Question 2 of 5
What is the time complexity of heapq.heapify()?
Question 3 of 5
How do you simulate a max heap using Python's heapq?
Question 4 of 5
In the "Kth Largest Element" problem, why do we use a min-heap of size k instead of a max-heap?
Question 5 of 5
In the "Merge K Sorted Lists" problem, what is the time complexity and why?
0
/5
Great work! You understand heaps and priority queues.

Next Lesson

Lesson 13: Tries →
Africa & India's Best AI Academy
🤖 AI-first 🎓 Placement Assistance

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 →