Topic 58 of 78
Min-Heap
Overview
A Min-Heap is a specialized Complete Binary Tree where the parent node is always smaller than or equal to its child nodes. This guarantees that the incredibly small minimum element is ALWAYS right at the very top (the root). While you can't search a Heap easily, it provides instant O(1) access to the minimum element, and O(log N) insertion and extraction. It is the underlying engine for Java's PriorityQueue.
Syntax
By doing a little math on array indices, we avoid the massive memory overhead of creating actual TreeNode objects.
Min-Heap using an Array
java
// Heaps are almost always implemented as Arrays, not Node objects!
// Parent index: (i - 1) / 2
// Left child: 2 * i + 1
// Right child: 2 * i + 2
public class MinHeap {
int[] heap = new int[100];
int size = 0;
public void insert(int val) {
heap[size] = val; // Add to bottom
int current = size;
size++;
// "Bubble Up" to restore heap property
while (current > 0 && heap[current] < heap[(current - 1) / 2]) {
swap(current, (current - 1) / 2);
current = (current - 1) / 2;
}
}
}Common Pitfalls
- Assuming a Min-Heap is fully sorted. It is NOT. Only the root is guaranteed to be the minimum. If you iterate through the array, the elements will look mostly random.
- Off-by-one errors when calculating child indices (`2i + 1` vs `2i`).
Interview Tips
- Always remember: Heaps are visually trees, but they are coded as simple Arrays. No node pointers are used.
Real-World Example
Dijkstra's Shortest Path algorithm relies on a Min-Heap to constantly fetch the nearest unvisited node instantly.
example
java
// Java provides a highly optimized Min-Heap out of the box
Queue<Node> minHeap = new PriorityQueue<>((a, b) -> a.distance - b.distance);
minHeap.offer(new Node("A", 10));
minHeap.offer(new Node("B", 5)); // Will be served first!