Min-Heap
Overview
A Min-Heap is a specialized Complete Binary Tree where every parent node is smaller than or equal to its children. Consequently, the absolute smallest element in the entire structure is always at the root node.
While conceptually a tree, Heaps are almost always implemented using a flat Array to save memory (no pointers needed!). The parent-child relationships are calculated using simple math: for a node at index i, its left child is at 2i + 1 and its right child is at 2i + 2.
Min-Heaps are the underlying engine of the PriorityQueue. They allow you to add new elements in O(log N) time, and extract the minimum element in O(log N) time. They are the backbone of algorithms like Dijkstra's Shortest Path and Prim's Minimum Spanning Tree.
Syntax
import java.util.PriorityQueue;
public class HeapDemo {
public static void main(String[] args) {
// By default, Java's PriorityQueue is a Min-Heap
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// Inserting elements (O(log N))
// Internally, it adds to the end of the array and "bubbles up"
minHeap.offer(45);
minHeap.offer(10);
minHeap.offer(25);
minHeap.offer(5);
// Peek views the minimum element without removing it (O(1))
System.out.println("Current Minimum: " + minHeap.peek()); // 5
// Extracting elements (O(log N))
// Internally, it removes the root, moves the last element to the root,
// and "sifts down" to restore the heap property
while (!minHeap.isEmpty()) {
System.out.println("Extracting: " + minHeap.poll());
}
// Output: 5, 10, 25, 45 (Sorted!)
}
}Common Pitfalls
- Iterating over a PriorityQueue expecting sorted order.
for(int x : minHeap)iterates over the underlying array structure. A heap only guarantees the root is the minimum, it does NOT guarantee the whole array is strictly sorted. You mustpoll()to get sorted output. - Attempting to search for an arbitrary element. Heaps are designed for O(1) access to the root. Finding an element that isn't the root requires scanning the entire array, which is O(N). If you need fast searches, use a TreeSet instead.
- Modifying objects inside the heap. If you add an object to a PriorityQueue and then change a property that affects its priority comparison, the heap will NOT automatically restructure. It will become corrupted. You must remove the object, update it, and re-add it.
Interview Questions
It uses level-order traversal. The root is at index 0. For any node at index i: its left child is at 2i + 1, its right child is at 2i + 2, and its parent is at (i - 1) / 2.
When a new element is inserted, it is placed at the very end of the internal array to maintain the 'Complete Tree' property. Then, we compare it with its parent. If it is smaller than its parent, they swap. We repeat this 'bubbling up' process until it reaches a parent that is smaller, or it becomes the new root.
Real-World Example
Operating Systems use Min-Heaps for Timer and Event Scheduling. If you have 1,000 background tasks scheduled to run at specific future times, the OS places them in a Min-Heap ordered by execution time. The task that needs to run soonest is always at the root, allowing the OS scheduler to sleep until that exact millisecond.
class Task implements Comparable<Task> {
String name;
long executionTimeMs;
public int compareTo(Task other) {
return Long.compare(this.executionTimeMs, other.executionTimeMs);
}
}
PriorityQueue<Task> taskScheduler = new PriorityQueue<>();
taskScheduler.offer(new Task("System Update", System.currentTimeMillis() + 60000));
taskScheduler.offer(new Task("Clear Cache", System.currentTimeMillis() + 5000));
// The scheduler simply checks the root to know when to wake up next
Task nextTask = taskScheduler.peek();
Thread.sleep(nextTask.executionTimeMs - System.currentTimeMillis());Check Your Knowledge
Test your understanding of Min-Heap with these quick questions.