Aku udah memakai priority queue sebelum membuat implementasinya sendiri. Membuat min heap ini membantuku mengikuti perubahan saat penambahan atau penghapusan merusak urutan antara parent dan child-nya.
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 aku bisa ambil elemen minimum dalam O(1) dan menghapusnya dalam O(log n).
Implementasi Min Heap Aku
Array menyimpan tree dari kiri ke kanan, satu level setiap urutan. Perhitungan index di bawah mencari parent dan child sebuah node.
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
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, aku 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
}
}
}
Biaya memperbaiki heap
Penambahan bisa bergerak dari level terakhir ke root. Penghapusan bisa bergerak dari root ke level terakhir. Complete binary tree punya O(log n) level, jadi setiap perbaikan butuh O(log n) waktu. Array-nya memakai O(n) space.
Membaca nilai minimum cuma perlu root, jadi butuh O(1) waktu. Sisa array nggak sepenuhnya terurut; yang dijamin cuma urutan antara setiap parent dan child-nya.

Memuat komentar...