Min Heap and Max Heap
Let's understand min-heap and max-heap with examples and operations.
Min-Heap
Every parent node is less than or equal to its children. The minimum element is always at the root.
// Min-heap array representation: [1, 3, 2, 5, 4, 6]
// 1
// /
// 3 2
// / /
//5 4 6
Max-Heap
Every parent node is greater than or equal to its children. The maximum element is at the root.
// Max-heap array representation: [6, 5, 4, 3, 2, 1]
// 6
// /
// 5 4
// / /
//3 2 1
Basic operations:
- peek() – return root (O(1))
- insert() – add element at end, then bubble up (O(log n))
- extract() – remove root, replace with last element, then bubble down (O(log n))
Two Minute Drill
- Min-heap: smallest at root, children larger.
- Max-heap: largest at root, children smaller.
- Insert: O(log n) with up-heap (bubble up).
- Extract root: O(log n) with down-heap (bubble down).
Need more clarification?
Drop us an email at career@quipoinfotech.com