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

Max-heap dalam bentuk binary tree dan array

Max-heap dalam bentuk binary tree dan array

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

Prosedur Max-heapify

Prosedur Max-heapify

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.

Ilustrasi Prosedur Max-Heapify

Ilustrasi Prosedur Max-Heapify

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

Prosedur BUILD-MAX-HEAP

Prosedur BUILD-MAX-HEAP

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.

Ilustrasi prosedur BUILD-MAX-HEAP

Ilustrasi prosedur BUILD-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.

Operasi heap sort setelah baris 1 untuk mencari nilai max-heap

Operasi heap sort setelah baris 1 untuk mencari nilai max-heap

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).

Ilustrasi Heap Sort

Ilustrasi Heap Sort

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].'&nbsp; &nbsp; &nbsp; &nbsp; ';

            }
            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].'&nbsp; &nbsp; &nbsp; &nbsp; ';
            }

        ?>
    </body>
</html>
Screenshot Program Pengurutan Metode Heap Sort

Screenshot Program Pengurutan Metode Heap Sort

Credited :

  1. IRWAN
  2. HALIM MUNAWAR
  3. M IQBAL PARABI
  4. EFENDI ZAENUDIN

“Deskripsi Heap Sort pada Tugas 1 Mata Kuliah Algoritma dan Pemrograman A – Magister IF STEI ITB 2013”

Heap Sort, Prosedur Heap Sort dan Source Code PHP



Comments

  1. By Efendi

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *