Advanced·2 min read
Heaps & HeapSort
Min/max heaps, heap operations, and the HeapSort algorithm.
Heaps & HeapSort
A heap is a complete binary tree satisfying the heap property.
Min-Heap vs Max-Heap
- Min-Heap: Parent ≤ Children (smallest at root)
- Max-Heap: Parent ≥ Children (largest at root)
``
Min-Heap: Max-Heap:
1 50
/ \ / \
3 2 30 40
/ \ / / \ /
7 4 5 10 20 35
`
Array Representation
For node at index i (0-based):
- Left child: 2i + 1
- Right child: 2i + 2
- Parent: (i - 1) // 2
`
Min-Heap array: [1, 3, 2, 7, 4, 5]
Index: 0 1 2 3 4 5
``
Heap Operations
| Header | ||
|---|---|---|
| Operation | Time | Process |
| Header | ||
|---|---|---|
| Insert (push up) | O(log n) | Add at end, bubble up |
| Extract min/max (push down) | O(log n) | Replace root, sift down |
| Build heap | O(n) | Start from last non-leaf, sift down |
| Peek min/max | O(1) | Just read root |
HeapSort
- Build a max-heap from the array
- Swap root (max) with last element
- Reduce heap size, sift down root
- Repeat until sorted
Priority Queue
Heaps are the standard implementation of priority queues - used in Dijkstra's algorithm, task scheduling, and more.
Code Example
python
import heapq
# Python's heapq implements a min-heap
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
heapq.heappush(heap, 1)
print("Min-heap:", heap)
print("Extract min:", heapq.heappop(heap))
print("After extract:", heap)
# Max-heap using negation
max_heap = []
for val in [5, 3, 7, 1, 9]:
heapq.heappush(max_heap, -val)
print("Max:", -heapq.heappop(max_heap))
# HeapSort implementation
def heapsort(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
sift_down(arr, n, i)
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
sift_down(arr, i, 0)
return arr
def sift_down(arr, n, i):
largest = i
left, right = 2 * i + 1, 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
sift_down(arr, n, largest)
data = [38, 27, 43, 3, 9, 82, 10]
print("HeapSorted:", heapsort(data.copy()))
# Top-K elements
nums = [3, 1, 5, 12, 2, 11]
print("Top 3:", heapq.nlargest(3, nums))
print("Bottom 3:", heapq.nsmallest(3, nums))Practice Problems
- 01Implement a max-heap from scratch using an array
- 02Find the median of a data stream using two heaps
- 03Merge k sorted arrays using a min-heap