Heap Sort, Prosedur Heap Sort dan Source Code PHP
Heap Sort – Heap adalah susunan data yang terstruktur dari array dirubah menjadi Complete Binary Tree (CBT). Setiap titik pada pohon menunjukkan suatu elemen pada array. Pohon biner menempati bagian tiap level hingga tingkat paling rendah dengan suatu kondisi dimulai dari kiri dan dapat berakhir di titik manapun hingga data yang terakhir.
Sebuah array A yang disebut dengan heap adalah suatu objek yang memiliki atribut, yaitu: A.length adalah jumlah elemen array dan A.heap-size adalah banyaknya elemen di dalam heap yang disimpan dengan array A. Elemen pada A.heap-size merupakan bagian elemen yang benar di dalam A.length dengan sebuah kondisi 0 ≤A[1. . A.heap-size] ≤A[1. . A.length]. Akar dari pohon heap adalah sebuah array A[1] dengan titik yang memiliki indeks i untuk menentukan parent, left child dan right child.
Heap Sort
Sebuah max-heap adalah binary tree yang memiliki nilai terbesar pada parent, dengan kata lain tidak ada node pada cabang yang memiliki nilai lebih besar dari akar (parent). Untuk mendapatkan nilai max-heap, dibutuhkan sebuah prosedur yang dinamakan MAX-HEAPIFY dengan input array A dan indeks i pada array tersebut.
MAX-HEAPIFY mengasumsikan pohon biner yang memiliki cabang kiri dan kanan; dan memiliki parent berupa max heap, tetapi sebuah array A[i] mungkin bernilai lebih kecil dari anaknya. Prosedur MAX-HEAPIFY menghasilkan semua nilai array A[i] selalu di bawah max-heap sehingga semua subtree yang berakar pada indeks i memenuhi sifat max-heap. Berikut prosedur MAX-HEAPIFY:
Prosedur Heap Sort
Pada setiap langkah, elemen terbesar A[i], A[LEFT(i)], dan A [RIGHT(i)] ditentukan dan mempunyai indeks tersimpan dalam largest. Jika array A[i] adalah largest, subtree yang berakar pada node i sudah merupakan sebuah max-heap dan prosedur berakhir. Dengan kata lain, satu dari dua child mempunyai elemen terbesar dan array A[i] ditukar dengan A[largest] yang mengakibatkan node i dan anaknya memenuhi sifat max-heap. Node dengan indeks largest, memiliki nilai asli A[i] dan subtree yang berakar pada largest mungkin tidak memenuhi sifat max-heap itu sendiri. Selanjutnya, prosedur MAX-HEAPIFY dapat dilakukan berulang pada subtree tersebut.
Prosedur MAX-HEAPIFY digunakan untuk mengkonversi array A[1…n] menjadi max heap dimana n adalah A.length. Sedangkan prosedur BUILD-MAX-HEAP melewati semua node pada tree, kemudian menjalankan MAX-HEAPIFY satu per satu.
Prosedur Heap Sort
Untuk menunjukkan prosedur BUILD-MAX-HEAP bekerja secara benar, digunakan perulangan invariant sebagai berikut :
“Awal dari setiap iterasi pada baris ke-2 s/d 3, setiap node i+1, i+2, … ,n adalah akar dari max-heap.”
Prosedur BUILD-MAX-HEAP dimulai dari Array [A.length/2] yang merupakan node dengan indeks terbesar yang memiliki anak, sampai berakhir pada node pertama A[1]. Fungsinya untuk memastikan bahwa semua node memiliki anak yang nilainya tidak lebih besar dari node tersebut. Iterasi dilakukan dari node terbesar [A.length/2] ke node terkecil A[1] untuk memastikan bahwa semua subtree dari anak sudah merupakan max-heap.
Algoritma Heap Sort dimulai dengan prosedur BUILD-MAX-HEAP untuk membangun max-heap pada array yang telah dimasukkan A[1 … n] dimana n=A.length. Elemen terbesar array disimpan di akar A[1], dimana A[1] ditetapkan sebagai posisi final, sehingga dapat ditukar dengan A[n]. Apabila node n dari heap dihilangkan dan A.heap-size akan semakin berkurang. Anak dari akar memenuhi ketentuan max-heap. Namn, elemen akar yang baru mungkin tidak memenuhi syarat max-heap. Untuk itu, diperlukan pemenuhan sifat max-heap yang disebut MAX-HEAPIFY(A,1) dimana menghasilkan sebuah max-heap A[1 . . n-1]. Algoritma heap sort mengulangi proses untuk max heap n-1 turun hingga heap-size 2.
Prosedur heapsort memerlukan waktu Θ(n log n), dimana prosedur BUILD-MAX-HEAP memerlukan waktu Θ(n) dan setiap n-1 melakukan prosedur max heapify memerlukan waktu Θ(log n).
Contoh kode pengurutan menggunakan metode heap sort (Code PHP) adalah sebagai berikut:
Source Code PHP
<!DOCTYPE html> <html> <title>Program Pengurutan menggunakan Metode Heapsort</title> <body> <?php function build_heap(&$array, $i, $t){ $tmp_var = $array[$i]; $j = $i * 2 + 1; while ($j <= $t){ if($j < $t){ if($array[$j] < $array[$j + 1]){ $j = $j + 1; } } if($tmp_var < $array[$j]){ $array[$i] = $array[$j]; $i = $j; $j = 2 * $i + 1; } else { $j = $t + 1; } } $array[$i] = $tmp_var; } function heap_sort(&$array){ $init = (int)floor((count($array)-1) / 2); for($i = $init; $i >= 0; $i--){ $count = count($array) - 1; build_heap($array, $i, $count); } for($i = (count($array) - 1); $i >= 1; $i--){ $tmp_var = $array[0]; $array [0] = $array [$i]; $array [$i] = $tmp_var; build_heap($array, 0, $i - 1); } } $array = array(); echo '<h3>Element Array Sebelum Terurut :</h3>'; for($p = 0; $p <= 49; $p++){ $array[$p] = rand(10,99); } for($i = 0; $i <= count($array)-1; $i++){ if($i%10 == 0) echo '<br />'; echo $array[$i].' '; } echo '<br /><br />'; echo '<h3>Element Array Setelah Terurut (Heap Sort):</h3>'; heap_sort($array); for($i = 0; $i <= count($array)-1; $i++){ if($i%10 == 0) echo '<br />'; echo $array[$i].' '; } ?> </body> </html>
Credited :
- IRWAN
- HALIM MUNAWAR
- M IQBAL PARABI
- EFENDI ZAENUDIN
“Deskripsi Heap Sort pada Tugas 1 Mata Kuliah Algoritma dan Pemrograman A – Magister IF STEI ITB 2013”
Kenangan yang tak terlupakan di semester I 2013. :-).