Heap Sort menggunakan struktur Heap (yang sudah kamu pelajari di Struktur Data) untuk mengurutkan data.

Kompleksitas: O(n log n) — selalu, tidak ada worst case yang lebih lambat. Space O(1) — in-place!

Cara kerja:

1. Build Max-Heap dari array (elemen terbesar di root)
2. Tukar root (terbesar) dengan elemen terakhir
3. Heapify root yang baru (perbaiki heap property)
4. Ulangi untuk sisa array

function heapSort(arr) {
  const n = arr.length;

  // Build max heap
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }

  // Extract max satu per satu
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]]; // Pindah max ke akhir
    heapify(arr, i, 0); // Perbaiki heap
  }

  return arr;
}

function heapify(arr, size, root) {
  let largest = root;
  const left = 2 * root + 1;
  const right = 2 * root + 2;

  if (left < size && arr[left] > arr[largest]) largest = left;
  if (right < size && arr[right] > arr[largest]) largest = right;

  if (largest !== root) {
    [arr[root], arr[largest]] = [arr[largest], arr[root]];
    heapify(arr, size, largest);
  }
}

heapSort([12, 11, 13, 5, 6, 7]);
// Build heap: [13, 11, 12, 5, 6, 7]
// Extract: 13→akhir, heapify → [12, 11, 7, 5, 6, 13]
// ... → [5, 6, 7, 11, 12, 13]

Perbandingan dengan sorting lain:

Kapan pakai Heap Sort?

• Butuh jaminan O(n log n) tanpa extra memory
• Embedded systems dengan memori terbatas
• Tapi di praktik, Quick Sort biasanya lebih cepat karena cache-friendly

🎭 Analogi sehari-hari: Heap Sort = pakai struktur "antrian prioritas" untuk sort. Bayangin tumpukan piring di IGD diurutin gawat darurat (max-heap). Ambil yang paling parah (root), tangani, lalu pasien berikutnya naik ke root. Ulangi. Hasil = pasien tertangani urut prioritas = sorted.

💡 Kenapa Heap Sort jarang dipakai walau O(n log n) konsisten? Konstanta lebih besar dan gak cache-friendly. Heapify melompat ke index 2i+1, 2i+2 — jauh-jauh, cache miss banyak. Quick Sort akses sequential = CPU cache happy. Praktiknya, Quick Sort dengan random pivot 2-3x lebih cepat untuk data biasa.

⚠️ Jebakan umum:

• Build heap dari atas (root) = O(n log n). Build dari belakang (bottom-up heapify) = O(n) — efisien
• heapify rekursif untuk heap besar = stack overflow. Pakai iteratif
• Salah index parent/child — parent = (i-1)/2, left = 2i+1, right = 2i+2. Hafalin
• Min-heap tapi mau ascending sort = harus pakai max-heap (atau negasi nilai)

🎯 Heap Sort vs lain:

• Embedded/memory-tight + worst-case matters → Heap Sort (no extra memory, O(n log n) jamin)
• Top-K elements (5 nilai terbesar dari 1jt) → pakai heap saja, gak full sort
• Default sort → Quick (cache-friendly) atau hybrid (TimSort)

🧪 Tebakan cepat: Cari 100 nilai terbesar dari 1 juta. Full sort? O(n log n). Pakai max-heap? Build O(n) + extract 100 = O(n + k log n). Heap saja untuk top-K.

TL;DR: Heap Sort = build heap, extract max berkali-kali. O(n log n) konsisten + O(1) space. Jaminan tanpa extra memory tapi cache-unfriendly. Foundation top-K problem.