Heaps — Min-Heap & Max-Heap Guide
In this tutorial, you'll learn about Heaps. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.
A heap is a specialized tree-based data structure that satisfies the heap property: in a max-heap, the parent is always greater than or equal to its children; in a min-heap, it's always smaller. Heaps are complete binary trees typically implemented as arrays.
What You'll Learn
You will learn heap operations (insert, extract, peek), building a heap from an array (heapify), heap sort, and priority queue implementation.
Why It Matters
Heaps enable O(log n) insertions and O(1) access to the min or max element. They are essential for priority queues, heap sort, Dijkstra's algorithm, and real-time event scheduling.
Real-World Use
Doda Browser's network request scheduler uses a min-heap as a priority queue. Critical requests (like main HTML) have high priority and are served before non-critical requests (like analytics). The heap ensures the highest-priority task is always processed next.
Max-Heap Array Representation
graph TD
R[50] --> L[30]
R --> RI[40]
L --> LL[20]
L --> LR[10]
RI --> RIL[35]
RI --> RIR[15]
style R fill:#4a90d9,stroke:#333,color:#fff
Array: [50, 30, 40, 20, 10, 35, 15]
For element at index i:
- Parent:
(i - 1) // 2 - Left child:
2 * i + 1 - Right child:
2 * i + 2
Max-Heap Implementation
class MaxHeap:
def __init__(self):
self.heap = []
def parent(self, i):
return (i - 1) // 2
def left_child(self, i):
return 2 * i + 1
def right_child(self, i):
return 2 * i + 2
def insert(self, value):
self.heap.append(value)
self._sift_up(len(self.heap) - 1)
def _sift_up(self, i):
while i > 0 and self.heap[i] > self.heap[self.parent(i)]:
self.heap[i], self.heap[self.parent(i)] = self.heap[self.parent(i)], self.heap[i]
i = self.parent(i)
def extract_max(self):
if not self.heap:
raise IndexError("heap is empty")
if len(self.heap) == 1:
return self.heap.pop()
max_val = self.heap[0]
self.heap[0] = self.heap.pop()
self._sift_down(0)
return max_val
def _sift_down(self, i):
while True:
largest = i
left = self.left_child(i)
right = self.right_child(i)
if left < len(self.heap) and self.heap[left] > self.heap[largest]:
largest = left
if right < len(self.heap) and self.heap[right] > self.heap[largest]:
largest = right
if largest != i:
self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
i = largest
else:
break
def peek(self):
if not self.heap:
raise IndexError("heap is empty")
return self.heap[0]
def size(self):
return len(self.heap)
max_heap = MaxHeap()
for v in [10, 20, 15, 30, 40]:
max_heap.insert(v)
print("Heap:", max_heap.heap)
print("Peek:", max_heap.peek())
print("Extract Max:", max_heap.extract_max())
print("Extract Max:", max_heap.extract_max())
print("Heap after extracts:", max_heap.heap)
Expected output:
Heap: [40, 30, 15, 10, 20]
Peek: 40
Extract Max: 40
Extract Max: 30
Heap after extracts: [20, 10, 15]
class MaxHeap {
constructor() { this.heap = []; }
parent(i) { return Math.floor((i - 1) / 2); }
leftChild(i) { return 2 * i + 1; }
rightChild(i) { return 2 * i + 2; }
insert(value) {
this.heap.push(value);
this._siftUp(this.heap.length - 1);
}
_siftUp(i) {
while (i > 0 && this.heap[i] > this.heap[this.parent(i)]) {
[this.heap[i], this.heap[this.parent(i)]] = [this.heap[this.parent(i)], this.heap[i]];
i = this.parent(i);
}
}
extractMax() {
if (!this.heap.length) throw new Error("heap is empty");
if (this.heap.length === 1) return this.heap.pop();
const maxVal = this.heap[0];
this.heap[0] = this.heap.pop();
this._siftDown(0);
return maxVal;
}
_siftDown(i) {
while (true) {
let largest = i;
const left = this.leftChild(i);
const right = this.rightChild(i);
if (left < this.heap.length && this.heap[left] > this.heap[largest]) largest = left;
if (right < this.heap.length && this.heap[right] > this.heap[largest]) largest = right;
if (largest !== i) {
[this.heap[i], this.heap[largest]] = [this.heap[largest], this.heap[i]];
i = largest;
} else break;
}
}
peek() { return this.heap[0]; }
size() { return this.heap.length; }
}
let maxHeap = new MaxHeap();
[10, 20, 15, 30, 40].forEach(v => maxHeap.insert(v));
console.log("Peek:", maxHeap.peek());
console.log("Extract Max:", maxHeap.extractMax());
console.log("Extract Max:", maxHeap.extractMax());
Expected output:
Peek: 40
Extract Max: 40
Extract Max: 30
Min-Heap (Using heapq)
Python's heapq module provides a min-heap implementation. JavaScript doesn't have a built-in heap.
import heapq
# Min-heap (default)
min_heap = [10, 20, 15, 30, 40]
heapq.heapify(min_heap) # Convert list to heap
print("Min-heap:", min_heap)
print("Peek:", min_heap[0])
print("Pop:", heapq.heappop(min_heap))
print("Pop:", heapq.heappop(min_heap))
heapq.heappush(min_heap, 5)
print("After push 5:", min_heap)
Expected output:
Min-heap: [10, 20, 15, 30, 40]
Peek: 10
Pop: 10
Pop: 15
After push 5: [5, 20, 40, 30]
Heapify: Building a Heap from an Array
Building a heap from an unsorted array in O(n) time:
def heapify(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
_sift_down(arr, n, i)
return arr
def _sift_down(arr, n, i):
while True:
largest = i
left = 2 * i + 1
right = 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]
i = largest
else:
break
print(heapify([3, 1, 6, 5, 2, 4]))
Expected output:
[6, 5, 4, 1, 2, 3]
Heap Sort
Heap sort uses a max-heap to sort in O(n log n) time in-place:
def heap_sort(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
arr = [12, 11, 13, 5, 6, 7]
print(heap_sort(arr))
Expected output:
[5, 6, 7, 11, 12, 13]
Common Pitfalls
1. Off-by-One in Parent/Child Indices
Using 0-based indexing: parent = (i-1)//2, children = 2*i+1 and 2*i+2. Confusing these breaks heap operations.
2. Not Sifting Both Directions
After an insert, sift up. After an extract, sift down. Using the wrong direction corrupts the heap property.
3. Assuming heapq Is a Max-Heap
Python's heapq is always a min-heap. Use negative values or tuple wrapping for max-heap behavior.
4. Forgetting the Complete Tree Invariant
Heaps must be complete binary trees. Arrays naturally maintain this, but linked implementations require careful node management.
5. Heapify vs Sift Complexity
Building a heap via repeated inserts takes O(n log n). Heapify (building from bottom-up) takes O(n). Always use heapify for bulk construction.
Practice Questions
1. Find the kth largest element in an array using a heap.
import heapq
def kth_largest(nums, k):
min_h = []
for num in nums:
heapq.heappush(min_h, num)
if len(min_h) > k:
heapq.heappop(min_h)
return min_h[0]
print(kth_largest([3, 2, 1, 5, 6, 4], 2))
Expected output: 5
2. Merge k sorted linked lists using a min-heap.
3. Find the median of a stream of numbers using two heaps.
4. Challenge: Implement a min-heap from scratch without using any built-in libraries, including heapify, insert, and extract_min.
5. Real-world task: Doda Browser's tab manager uses a max-heap to prioritize tabs by memory usage. Write a function that takes a list of tabs (with memory usage) and returns the top 3 tabs with highest memory usage, ready for suspension.
What's Next
Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.
Built by the developers of DodaTech
Doda Browser, DodaZIP & Durga Antivirus Pro