Heaps
Priority queues with O(1) min/max access
The Heap Property
A heap is a complete binary tree where each parent satisfies the heap property. In a min heap, parents are smaller than children; in a max heap, parents are larger. Heaps are perfect for priority queues where you always need the min or max.
Key Insight
Heaps are typically stored in arrays. For node at index i: parent = (i-1)/2, left child = 2i+1, right child = 2i+2.
Use Cases
- • Priority queues (task scheduling)
- • Heap sort algorithm
- • Finding k largest/smallest elements
- • Graph algorithms (Dijkstra's)
Tree View
Purple = Minimum (root)
Array View
10
[0]
20
[1]
30
[2]
40
[3]
50
[4]
35
[5]
45
[6]
For index i:
Parent: ⌊(i-1)/2⌋
Left child: 2i + 1
Right child: 2i + 2
Complexity Analysis
| Operation | Complexity | Notes |
|---|---|---|
| Get min/max | O(1) | Always at root (index 0) |
| Insert | O(log n) | Add at end, bubble up |
| Extract min/max | O(log n) | Replace root, bubble down |
| Build heap | O(n) | Bottom-up heapify is more efficient than repeated insert |