Eduzan / DSA in Python
Heaps in Python
Worked examples are fully visible. Check-yourself items are study aids you can reveal one at a time.
A heap is a specialized tree-based structure that satisfies the heap property. Heaps are commonly used to implement priority queues, scheduling systems, and efficient selection problems (top-k).
Min-Heap
- Smallest element at the root
- Parent <= children
Max-Heap
- Largest element at the root
- Parent >= children
Important: Heaps are not fully sorted; they only guarantee ordering between parent and child.
Python uses arrays (lists) internally for heaps. For a node at index i:
- left child =
2*i + 1 - right child =
2*i + 2 - parent =
(i - 1) // 2
Python provides min-heap via heapq.
import heapq
heap = []
heapq.heappush(heap, 10)
heapq.heappush(heap, 5)
heapq.heappush(heap, 20)
print(heap) # [5, 10, 20]
Insertion (Push) — O(log n)
heapq.heappush(heap, 3)
Deletion (Pop smallest) — O(log n)
smallest = heapq.heappop(heap)
print(smallest)
Peek — O(1)
print(heap[0])
Heapify — O(n)
Converts a normal list into a heap efficiently.
nums = [10, 3, 5, 7]
heapq.heapify(nums)
print(nums)
Python supports min-heap only, but you can simulate max-heap using negatives.
import heapq
max_heap = []
heapq.heappush(max_heap, -10)
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -20)
print(-heapq.heappop(max_heap)) # 20
- Priority queue (tasks, CPU scheduling)
- Dijkstra algorithm (shortest path)
- Top K elements
- Merge K sorted lists
- Heap sort
Example: Top K largest elements
import heapq
nums = [5, 12, 3, 21, 7, 9]
k = 3
print(heapq.nlargest(k, nums)) # [21, 12, 9]
Heaps are essential when you need repeated access to the smallest/largest element efficiently. Master heapq, and many interview problems (top-k, scheduling, shortest path) become straightforward.
End of lesson.