I built a minimum heap to understand how a priority queue stores and removes items. The implementation showed me how the heap maintains the smallest value at its root.
What Is a Min Heap?
A min heap is a binary tree where:
- The parent is always smaller than or equal to its children
- The root is the smallest element
- It is a complete binary tree (filled left to right)
This structure lets me get the minimum element in O(1) and remove it in O(log n).
Why I Wanted to Understand It
I used priority queues in my code before I understood their implementation. I wanted to see how each insertion and removal preserved the heap property.
My Min Heap Implementation
I implemented it using an array (which is how heaps are typically stored):
class MinHeap {
constructor() {
this.heap = [];
}
// Helper methods to navigate the tree
getParentIndex(i) {
return Math.floor((i - 1) / 2);
}
getLeftChildIndex(i) {
return 2 * i + 1;
}
getRightChildIndex(i) {
return 2 * i + 2;
}
// Add element to heap
add(value) {
this.heap.push(value);
this.heapifyUp(); // Maintain heap property
}
// Remove and return minimum element
poll() {
if (this.heap.length === 0) return null;
if (this.heap.length === 1) {
return this.heap.pop();
}
const root = this.heap[0];
this.heap[0] = this.heap.pop(); // Move last element to root
this.heapifyDown(); // Maintain heap property
return root;
}
// Move element up to maintain heap property
heapifyUp() {
let index = this.heap.length - 1;
while (index > 0) {
const parentIndex = this.getParentIndex(index);
// If parent is smaller or equal, we're done
if (this.heap[parentIndex] <= this.heap[index]) {
break;
}
// Swap with parent
[this.heap[index], this.heap[parentIndex]] =
[this.heap[parentIndex], this.heap[index]];
index = parentIndex;
}
}
// Move element down to maintain heap property
heapifyDown() {
let index = 0;
while (this.getLeftChildIndex(index) < this.heap.length) {
const leftIndex = this.getLeftChildIndex(index);
const rightIndex = this.getRightChildIndex(index);
let smallerChildIndex = leftIndex;
// Find smaller child
if (rightIndex < this.heap.length &&
this.heap[rightIndex] < this.heap[leftIndex]) {
smallerChildIndex = rightIndex;
}
// If current is smaller than both children, we're done
if (this.heap[index] <= this.heap[smallerChildIndex]) {
break;
}
// Swap with smaller child
[this.heap[index], this.heap[smallerChildIndex]] =
[this.heap[smallerChildIndex], this.heap[index]];
index = smallerChildIndex;
}
}
isEmpty() {
return this.heap.length === 0;
}
}
How It Works
Adding an element:
- Add to the end of the array
- "Bubble up" by comparing with parent
- Swap if parent is larger
- Repeat until heap property is restored
Removing minimum:
- Remove root (minimum)
- Move last element to root
- "Bubble down" by comparing with children
- Swap with smaller child if needed
- Repeat until heap property is restored
Testing It
const minHeap = new MinHeap();
minHeap.add(10);
minHeap.add(5);
minHeap.add(20);
minHeap.add(1);
while (!minHeap.isEmpty()) {
console.log(minHeap.poll()); // Prints: 1, 5, 10, 20
}
Java's Built in PriorityQueue
In Java, I can use the built in PriorityQueue, which is a min heap by default:
import java.util.PriorityQueue;
public class MinHeapExample {
public static void main(String[] args) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.add(10);
minHeap.add(5);
minHeap.add(20);
minHeap.add(1);
while (!minHeap.isEmpty()) {
System.out.println(minHeap.poll()); // Prints: 1, 5, 10, 20
}
}
}
What I Learned
Implementing a heap from scratch taught me:
- How the array representation works (parent at i, children at 2i+1 and 2i+2)
- Why heapify operations are O(log n)
- How the heap property is maintained
- Why heaps are well suited to priority queues
Key Takeaways
- Min heaps keep the minimum at the root
- Array representation is efficient (no pointers needed)
- Heapify operations maintain the heap property
- O(log n) insert and remove, O(1) peek at minimum
Loading comments...