Bagaimana Cara Kerjanya?

Binary heap berada di dalam array biasa. Untuk node pada indeks i (berbasis 0), anak-anaknya berada pada indeks 2*i + 1 dan 2*i + 2. Pengindeksan inilah trik yang memungkinkan tree berada di dalam array.

Proses Langkah demi Langkah:

1. Buat max-heap: susun ulang array sehingga setiap parent >= anak-anaknya. Nilai terbesar berada di indeks 0.
2. Ambil nilai maksimum: tukar root (terbesar) dengan elemen terakhir heap, lalu kurangi ukuran heap satu agar nilai terbesar kini berada di bagian akhir pada posisi finalnya dalam urutan.
3. Perbaiki dengan sift-down: root yang baru mungkin tidak berada di posisi yang tepat, jadi turunkan dengan sift (tukar dengan anaknya yang lebih besar, ulangi) sampai properti heap terpenuhi lagi.
4. Ulangi sampai heap kosong. Array kini terurut menaik.

Contoh pada [4, 10, 3, 5, 1]:

• Buat max-heap: [10, 5, 3, 4, 1].
• Tukar root 10 ke bagian akhir dan lakukan sift-down, lalu ulangi untuk 5, 4, 3.
• Hasil: [1, 3, 4, 5, 10].