Min Heap
Definition
A Min Heap is the exact opposite of a Max Heap. In a Min Heap, the value of every parent node is less than or equal to the values of its children. The smallest number is always at the root.
How it Works
- The Rule: Every parent must be smaller than its children.
- The Root: The top-most element is always the absolute minimum value in the entire dataset.
Example
Input Numbers: [10, 20, 15, 30, 40]
Min Heap Structure:
10
/ \
20 15
/ \
30 40
Notice that 10 is smaller than 20 and 15. 20 is smaller than 30 and 40.
Code Example
PythonJavaCC++
import heapq
# Python's default heap implementation is a Min Heap
min_heap = []
numbers = [40, 30, 15, 10, 20]
# Build the heap
for num in numbers:
heapq.heappush(min_heap, num)
# The smallest element is always at index 0
print("Smallest value:", min_heap[0]) # Output: 10
# Remove the smallest element
smallest = heapq.heappop(min_heap)
print("Removed:", smallest) # Output: 10
import java.util.PriorityQueue;
public class MinHeapExample {
public static void main(String[] args) {
// Java PriorityQueue default = Min Heap
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
int[] numbers = {40, 30, 15, 10, 20};
// Insert elements
for (int num : numbers) {
minHeap.add(num);
}
// Smallest element
System.out.println("Smallest value: " + minHeap.peek()); // 10
// Remove smallest element
int smallest = minHeap.poll();
System.out.println("Removed: " + smallest); // 10
}
}
#include <stdio.h>
#define SIZE 100
int heap[SIZE];
int n = 0;
// Insert into Min Heap
void insert(int value) {
int i = n++;
heap[i] = value;
// Heapify up
while (i != 0 && heap[(i - 1) / 2] > heap[i]) {
int temp = heap[i];
heap[i] = heap[(i - 1) / 2];
heap[(i - 1) / 2] = temp;
i = (i - 1) / 2;
}
}
// Remove smallest element
int extractMin() {
int root = heap[0];
heap[0] = heap[--n];
int i = 0;
while (1) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int smallest = i;
if (left < n && heap[left] < heap[smallest])
smallest = left;
if (right < n && heap[right] < heap[smallest])
smallest = right;
if (smallest != i) {
int temp = heap[i];
heap[i] = heap[smallest];
heap[smallest] = temp;
i = smallest;
}
else
break;
}
return root;
}
int main() {
int numbers[] = {40,30,15,10,20};
for (int i = 0; i < 5; i++)
insert(numbers[i]);
printf("Smallest value: %d\n", heap[0]);
int smallest = extractMin();
printf("Removed: %d\n", smallest);
return 0;
}
#include <iostream>
#include <queue>
using namespace std;
int main() {
// Min Heap in C++
priority_queue<int, vector<int>, greater<int>> minHeap;
int numbers[] = {40,30,15,10,20};
for (int i = 0; i < 5; i++)
minHeap.push(numbers[i]);
cout << "Smallest value: " << minHeap.top() << endl;
int smallest = minHeap.top();
minHeap.pop();
cout << "Removed: " << smallest << endl;
return 0;
}
Use Cases
- Merging Sorted Arrays: Efficiently combining multiple sorted lists into one.
- Real-time Stream Data: Finding the median of a number stream dynamically.