Heap sort mengurutkan array dengan terus mengambil angka terbesar dan menaruhnya di ujung belakang. Supaya angka terbesar selalu gampang ditemukan, array-nya disusun dulu jadi heap. Mirip antrean IGD: pasien paling gawat selalu dipanggil duluan, dan setelah dia ditangani, yang paling gawat berikutnya naik ke depan.
🧪 Tebakan cepat: kalau array sudah jadi max-heap, apakah array itu sudah terurut? Tebak dulu, jawabannya ada di bagian "Heap, lalu ambil yang terbesar".
Heap, lalu ambil yang terbesar
Max-heap adalah array yang dibaca sebagai pohon: angka di index i punya dua anak, di index 2i + 1 dan 2i + 2. Aturannya cuma satu: tiap parent (induk) lebih besar atau sama dengan anak-anaknya, jadi angka terbesar selalu ada di index 0, yang disebut root.
array: [13, 11, 12, 5, 6, 7]
13 index 0 (root)
/ \
11 12 index 1 dan 2
/ \ /
5 6 7 index 3, 4, 5
Array ini max-heap (13 di atas 11 dan 12, 11 di atas 5 dan 6, 12 di atas 7), tapi belum terurut: 11 masih di depan 12. Itu jawaban tebakannya: heap cuma menjamin root-nya yang terbesar.
Heap sort jalan dalam dua fase. Ini yang terjadi pada [12, 11, 13, 5, 6, 7]:
| Langkah | Heap | Sudah di tempatnya |
|---|---|---|
| Awal | [12, 11, 13, 5, 6, 7] |
|
| Fase 1: bangun max-heap | [13, 11, 12, 5, 6, 7] |
|
| Tukar 13 ke ujung, perbaiki heap | [12, 11, 7, 5, 6] |
[13] |
| Tukar 12 ke ujung, perbaiki heap | [11, 6, 7, 5] |
[12, 13] |
| Tukar 11 ke ujung, perbaiki heap | [7, 6, 5] |
[11, 12, 13] |
| Ulangi sampai heap habis | [5, 6, 7, 11, 12, 13] |
function heapSort(arr) {
const n = arr.length;
// fase 1: bangun max-heap, mulai dari parent terakhir
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) heapify(arr, n, i);
// fase 2: tukar root (terbesar) ke ujung, heap menyusut satu
for (let i = n - 1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]];
heapify(arr, i, 0);
}
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); // terus turun sampai aman
}
}
console.log(heapSort([12, 11, 13, 5, 6, 7]));
// [5, 6, 7, 11, 12, 13]
heapify(arr, size, root)membetulkan satu titik: bandingkanrootdengan dua anaknya. Kalau ada anak yang lebih besar, tukar, lalu lanjut turun dari posisi barunya (heapify memanggil dirinya sendiri).sizeadalah batas heap. Angka di belakangsizesudah di tempatnya dan gak disentuh lagi.- Fase 1 memanggil
heapifydari parent terakhir,Math.floor(n / 2) - 1, mundur sampai index 0. - Fase 2: root pasti yang terbesar, jadi ditukar ke ujung. Heap menyusut satu, lalu
heapify(arr, i, 0)menaikkan yang terbesar berikutnya ke root. [a, b] = [b, a]adalah cara singkat menukar dua isi.
Cepat dan hemat, tapi jarang dipakai
Big-O bilang seberapa cepat kerja algoritma bertambah saat datanya bertambah. O(n) artinya datanya dua kali lipat, waktunya kira-kira dua kali lipat.
- Pohonnya cuma setinggi log n level (1.000 angka: sekitar 10 level). Tiap kali root diambil, heapify turun paling banyak setinggi itu, dan ini diulang n kali. Totalnya O(n log n) di semua kasus: terbaik, rata-rata, dan terburuk.
- Semuanya terjadi di array yang sama, tanpa array tambahan: memori tambahannya O(1).
- Heap sort gak stabil: data yang nilainya sama bisa tertukar urutannya.
Kenapa jarang dipakai? heapify melompat-lompat ke index 2i + 1 dan 2i + 2 yang letaknya berjauhan. CPU punya cache, memori kecil yang super cepat dan memuat data yang letaknya berdekatan sekaligus. Lompatan jauh bikin cache sering meleset. Quick sort dan merge sort membaca data berurutan, jadi di praktik biasanya lebih cepat, walau Big-O-nya setara.
⚠️ Jebakan yang sering ketemu
- Min-heap untuk urutan naik. Cara ini memindahkan yang terbesar ke belakang duluan, jadi untuk hasil kecil ke besar butuh max-heap. Min-heap menghasilkan urutan turun.
- Index anak salah. Karena index mulai dari 0, anak dari
iada di2 * i + 1dan2 * i + 2, bukan2 * i. sizeyang gak menyusut. Di fase 2,heapifyharus pakaii, bukann. Kalau pakain, angka yang sudah di tempatnya ditarik balik ke heap.
TL;DR: Max-heap adalah array yang dibaca sebagai pohon (anak dari i di 2i + 1 dan 2i + 2), dengan tiap parent lebih besar dari anaknya, jadi root di index 0 selalu yang terbesar. Heap sort membangun max-heap, lalu berulang kali menukar root ke ujung dan memperbaiki heap yang menyusut. Selalu O(n log n), memori tambahan O(1), gak stabil. Jarang dipakai karena lompatannya bikin cache CPU sering meleset.
