WikiGalaxy
Introduction to Min Heap
Definition
A Min Heap is a complete binary tree where the value of each node is less than or equal to the values of its children. The root node contains the smallest element.
Applications
Min Heaps are commonly used in algorithms like Dijkstra's shortest path and Prim's minimum spanning tree.
Example 1: Basic Min Heap
Inserting Elements
Insert elements into the heap while maintaining the min heap property.
import java.util.PriorityQueue;
public class MinHeapExample {
public static void main(String[] args) {
PriorityQueue minHeap = new PriorityQueue<>();
minHeap.add(10);
minHeap.add(5);
minHeap.add(15);
minHeap.add(3);
System.out.println("Min Heap: " + minHeap);
}
}
Console Output:
Min Heap: [3, 5, 15, 10]
Example 2: Extracting Minimum
Extract Minimum Element
Remove the smallest element from the heap.
import java.util.PriorityQueue;
public class MinHeapExtract {
public static void main(String[] args) {
PriorityQueue minHeap = new PriorityQueue<>();
minHeap.add(10);
minHeap.add(5);
minHeap.add(15);
minHeap.add(3);
int minElement = minHeap.poll();
System.out.println("Extracted Minimum: " + minElement);
System.out.println("Min Heap after extraction: " + minHeap);
}
}
Console Output:
Extracted Minimum: 3
Min Heap after extraction: [5, 10, 15]
Example 3: Decreasing Key Value
Decrease Key Operation
Decrease the value of a key and adjust the heap accordingly.
import java.util.PriorityQueue;
import java.util.Iterator;
public class MinHeapDecreaseKey {
public static void main(String[] args) {
PriorityQueue minHeap = new PriorityQueue<>();
minHeap.add(10);
minHeap.add(5);
minHeap.add(15);
minHeap.add(3);
// Decrease key by removing and adding
minHeap.remove(10);
minHeap.add(2);
System.out.println("Min Heap after decreasing key: " + minHeap);
}
}
Console Output:
Min Heap after decreasing key: [2, 3, 15, 5]
Example 4: Building a Min Heap
Building from Array
Construct a min heap from an existing array of elements.
import java.util.PriorityQueue;
public class MinHeapBuild {
public static void main(String[] args) {
int[] elements = {10, 5, 15, 3};
PriorityQueue minHeap = new PriorityQueue<>();
for (int element : elements) {
minHeap.add(element);
}
System.out.println("Built Min Heap: " + minHeap);
}
}
Console Output:
Built Min Heap: [3, 5, 15, 10]
Example 5: Merging Two Min Heaps
Merge Operation
Combine two min heaps into a single min heap.
import java.util.PriorityQueue;
public class MinHeapMerge {
public static void main(String[] args) {
PriorityQueue minHeap1 = new PriorityQueue<>();
minHeap1.add(10);
minHeap1.add(5);
PriorityQueue minHeap2 = new PriorityQueue<>();
minHeap2.add(15);
minHeap2.add(3);
minHeap1.addAll(minHeap2);
System.out.println("Merged Min Heap: " + minHeap1);
}
}
Console Output:
Merged Min Heap: [3, 5, 15, 10]
