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 terkecil) Max-Heap: Parent ≥ Child (root = nilai terbesar)

Operasi dan kompleksitas:

class MinHeap {
  constructor() {
    this.heap = [];
  }

  insert(value) {
    this.heap.push(value);
    this._bubbleUp(this.heap.length - 1);
  }

  extractMin() {
    if (this.heap.length === 0) return undefined;
    const min = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this._sinkDown(0);
    }
    return min;
  }

  _bubbleUp(i) {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (this.heap[parent] <= this.heap[i]) break;
      [this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
      i = parent;
    }
  }

  _sinkDown(i) {
    const n = this.heap.length;
    while (true) {
      let smallest = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      if (left < n && this.heap[left] < this.heap[smallest]) smallest = left;
      if (right < n && this.heap[right] < this.heap[smallest]) smallest = right;
      if (smallest === i) break;
      [this.heap[smallest], this.heap[i]] = [this.heap[i], this.heap[smallest]];
      i = smallest;
    }
  }
}

Kegunaan nyata:

• Priority Queue — antrian dengan prioritas (ER triage, task scheduling)
• Heap Sort — sorting O(n log n)
• Dijkstra — shortest path algorithm
• Median finder — gunakan min-heap + max-heap

🎭 Analogi sehari-hari: Heap = ruang IGD rumah sakit. Bukan urut datang (queue biasa), tapi urut prioritas medis. Yang paling kritis (root) ditangani duluan, gak peduli kapan dia tiba. Setiap pasien baru masuk → diatur sesuai gawatnya. Itu Priority Queue.

💡 Kenapa Heap pakai Array, bukan pointer? Heap adalah complete binary tree — pasti penuh dari kiri. Karena strukturnya predictable, bisa di-encode di array dengan rumus index:

• Parent dari index i = (i-1)/2
• Left child = 2i+1
• Right child = 2i+2

Hasilnya: hemat memori (no pointer) + cache friendly (compact array).

⚠️ Jebakan umum:

• Tidak balanced setelah extract kalau lupa bubbleUp/sinkDown — heap rusak
• Sort dengan heap = O(n log n) tapi quicksort sering lebih cepat di praktik (cache locality)
• Priority Queue di JS tidak built-in — harus implementasi sendiri atau pakai library
• Min-heap tapi ngambil max = salah, swap perbandingan atau pakai max-heap

🎯 Stack vs Queue vs Priority Queue:

• Stack: "yang baru duluan" → undo
• Queue: "yang dateng dulu duluan" → fairness antrian
• Priority Queue: "yang penting duluan" → triage, scheduler, Dijkstra

🧪 Tebakan cepat: Cari k elemen terkecil dari 1jt data. Brute sort O(n log n). Pakai max-heap size k → O(n log k) — kalau k kecil, jauh lebih cepat.

TL;DR: Heap = priority queue, parent ≤ children (min) atau ≥ (max). Insert/extract O(log n), peek O(1). Foundation Dijkstra dan banyak algoritma top-k.