Saya bikin minimum heap untuk memahami gimana priority queue menyimpan dan mengeluarkan item. Dari implementasinya, saya jadi lihat gimana heap menjaga nilai terkecil tetap ada di root.
Apa Itu Min Heap?
Min heap adalah binary tree yang:
- Parent-nya selalu lebih kecil atau sama dengan child-nya
- Root-nya adalah elemen terkecil
- Bentuknya complete binary tree (diisi dari kiri ke kanan)
Struktur ini bikin saya bisa ambil elemen minimum dalam O(1) dan menghapusnya dalam O(log n).
Kenapa Saya Pengin Memahaminya
Saya udah pakai priority queue di kode saya sebelum paham implementasinya. Saya pengin lihat gimana setiap penambahan dan penghapusan tetap menjaga heap property.
Implementasi Min Heap Saya
Saya mengimplementasikannya pakai array (memang begitu biasanya heap disimpan):
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;
}
}
Cara Kerjanya
Menambahkan elemen:
- Tambahkan ke ujung array
- "Bubble up" dengan membandingkannya ke parent
- Tukar kalau parent lebih besar
- Ulangi sampai heap property kembali terpenuhi
Menghapus minimum:
- Hapus root (minimum)
- Pindahkan elemen terakhir ke root
- "Bubble down" dengan membandingkannya ke child
- Tukar dengan child yang lebih kecil kalau perlu
- Ulangi sampai heap property kembali terpenuhi
Mengujinya
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
}
PriorityQueue Bawaan Java
Di Java, saya bisa pakai PriorityQueue bawaan, yang secara default adalah min heap:
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
}
}
}
Yang Saya Pelajari
Mengimplementasikan heap dari nol mengajari saya:
- Gimana representasi array bekerja (parent di i, child di 2i+1 dan 2i+2)
- Kenapa operasi heapify itu O(log n)
- Gimana heap property dijaga
- Kenapa heap cocok untuk priority queue
Poin Penting
- Min heap menyimpan nilai minimum di root
- Representasi array itu efisien (nggak butuh pointer)
- Operasi heapify menjaga heap property
- Insert dan remove O(log n), peek nilai minimum O(1)
Memuat komentar...