Priority queue adalah antrean yang melayani yang paling penting dulu, bukan yang datang duluan. Kayak IGD rumah sakit: pasien paling gawat ditangani pertama, kapan pun dia datang. Cara paling umum membuatnya adalah heap. Di min-heap, tiap parent lebih kecil atau sama dengan anak-anaknya, jadi angka terkecil selalu ada di root, paling atas. Max-heap kebalikannya: yang terbesar di root.
🧪 Tebakan cepat: min-heap berisi
[1, 3, 5, 7, 9]. Setelah 1 diambil, angka mana yang jadi root baru: 3, 5, atau 9? Tebak dulu, jawabannya ada di bagian "extractMin: ambil root, lalu turunkan penggantinya".
Heap disimpan di array
2 index: 0 1 2 3 4 5
/ \ array: [2, 4, 6, 8, 10, 12]
4 6
/ \ /
8 10 12
- Heap diisi level demi level dari kiri, tanpa bolong, jadi bisa disimpan rapat di array. Root ada di index 0.
- Anak dari index
iada di index2 * i + 1(kiri) dan2 * i + 2(kanan). Anak dari 4 (index 1) ada di index 3 dan 4: angka 8 dan 10. - Parent dari index
iada di indexMath.floor((i - 1) / 2). Parent dari 12 (index 5) ada di index 2: angka 6. - Aturannya cuma antara parent dan anak: 2 ≤ 4, 2 ≤ 6, 4 ≤ 8, dan seterusnya. Antar saudara gak diatur, jadi array heap belum tentu terurut.
insert: masuk di belakang, lalu naik
Angka baru selalu ditaruh di paling belakang array. Selama dia lebih kecil dari parent-nya, tukar dengan parent itu (namanya sift up). Contoh: insert(1) ke heap tadi.
| Langkah | Array | Yang terjadi |
|---|---|---|
| 1 | [2, 4, 6, 8, 10, 12, 1] |
1 masuk di index 6. Parent-nya di index 2: angka 6 |
| 2 | [2, 4, 1, 8, 10, 12, 6] |
1 < 6: tukar. Sekarang di index 2, parent-nya angka 2 |
| 3 | [1, 4, 2, 8, 10, 12, 6] |
1 < 2: tukar. Sampai di root: berhenti |
Kalau parent-nya sudah lebih kecil, angka baru berhenti lebih awal.
extractMin: ambil root, lalu turunkan penggantinya
Root diambil sebagai hasil. Angka paling belakang pindah ke root, lalu turun: selama ada anak yang lebih kecil, tukar dengan anak yang paling kecil (namanya sift down). Contoh: extractMin() pada [1, 3, 5, 7, 9].
| Langkah | Array | Yang terjadi |
|---|---|---|
| 1 | [9, 3, 5, 7] |
1 diambil, 9 (paling belakang) pindah ke root |
| 2 | [3, 9, 5, 7] |
anak 9 adalah 3 dan 5. Yang terkecil 3, dan 3 < 9: tukar |
| 3 | [3, 7, 5, 9] |
anak 9 sekarang cuma 7. 7 < 9: tukar. Gak ada anak lagi: berhenti |
Hasilnya 1, dan heap-nya jadi [3, 7, 5, 9]. Root barunya 3, angka terkecil berikutnya. Itu jawaban tebakannya.
Seberapa cepat? Melihat yang terkecil cukup membaca index 0: O(1), waktunya tetap. insert dan extractMin paling banyak naik atau turun setinggi pohonnya, dan tinggi heap cuma sekitar log n: 1.000 data sekitar 10 level, 1.000.000 data sekitar 20 level. Jadi keduanya O(log n).
Memakai heap: ambil k angka terkecil
Class MinHeap di latihan sudah punya insert, extractMin, dan size. Kamu tinggal memakainya:
const heap = new MinHeap();
for (const angka of [5, 2, 8, 1]) heap.insert(angka);
console.log(heap.extractMin()); // 1
console.log(heap.extractMin()); // 2
console.log(heap.size()); // 2 (sisa 5 dan 8)
Tiap extractMin() memberi angka terkecil yang tersisa. Jadi untuk k angka terkecil: masukkan semuanya, panggil extractMin() k kali di dalam loop, dan kumpulkan hasilnya di array. Urutannya otomatis dari kecil.
⚠️ Jebakan yang sering ketemu
- Berhenti turun terlalu cepat. Pengganti di root harus terus turun selama masih ada anak yang lebih kecil, bukan cuma sekali tukar. Di contoh tadi, 9 turun dua kali.
- Tukar dengan anak yang salah. Waktu turun, tukar dengan anak yang lebih kecil. Kalau dengan yang lebih besar, anak yang kecil berakhir di bawah angka yang lebih besar, dan heap-nya rusak.
- Mengira heap sudah terurut.
[1, 4, 2, 8, 10, 12, 6]adalah heap yang sah, tapi gak terurut. Yang dijamin cuma root-nya yang terkecil. Mau urut? Ambil satu per satu pakaiextractMin(). - Pakai
sortdi latihan.sortjuga memberi angka yang benar, tapi latihannya memeriksa kamu membuatnew MinHeap()dan memanggilextractMin().
TL;DR: Priority queue melayani yang paling penting dulu, dan heap adalah cara membuatnya. Min-heap menjaga tiap parent ≤ anaknya, jadi yang terkecil selalu di root (index 0). Anak index i ada di 2 * i + 1 dan 2 * i + 2, parent-nya di Math.floor((i - 1) / 2). insert menaruh di belakang lalu naik; extractMin mengambil root, memindah yang paling belakang ke root, lalu menurunkannya. Melihat root O(1), insert dan extract O(log n).
