Heap / Priority Queue — Struktur Data

Heap adalah binary tree khusus di mana parent selalu lebih kecil (min-heap) atau lebih besar (max-heap) dari child-nya. Min-Heap: Parent ≤ Child (root = nilai…

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 i ada di index 2 * i + 1 (kiri) dan 2 * i + 2 (kanan). Anak dari 4 (index 1) ada di index 3 dan 4: angka 8 dan 10.
Parent dari index i ada di index Math.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 pakai extractMin().
Pakai sort di latihan. sort juga memberi angka yang benar, tapi latihannya memeriksa kamu membuat new MinHeap() dan memanggil extractMin().

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).