Heap Sort

Heap Sort, apa sih Heap Sort? Penjelasan singkatnya adalah Heap sort merupakan salah satu metode pengurutan data dari suatu array yang digambarkan menjadi sebuah pohon atau tree dan nilai pada masing-masing indeksnya akan diurutkan.

Pada metode ini memiliki 3 bagian, yaitu Node, Root, Link, dan Leaf. Apa sih itu? Node adalah indeks yang berada pada array, root adalah node awal pada tree, link adalah sebuah garis yang menyambungkan antara node satu ke node lainnya, dan Leaf adalah node yang tidak memiliki anak atau tidak memiliki node turunan. Untuk ilustrasinya bisa dilihat dari gambar dibawah ini.

Contoh dari Heap Tree dapat dilihat dibawah ini.

Adapun proses dari Heap Sort :

1. Pembentukan Heap
2. Pengurutan Data pada Heap

Pada pembentukan Heap adapun cara-caranya yaitu dengan,

Dari sebuah array dibuat menjadi Complete Binary Tree, lalu

Jika sudah menjadi CBT lalu lakukan proses pengurutan secara max heap dengan cara banyaknya simpul dibagi dua untuk mencari nilai tengah dari sebuah array, sebagai contoh N = 6, Tengah = 6/2 = 3. Lalu lakukan reorganisasi pada simpul atau node ke-3. Dengan cara jika angka yang sekarang dibandingkan dengan angka selanjutnya yang ada di node turunannya itu lebih kecil maka tukar posisi.

Lalu, lakukan reorganisasi pada simpul ke-2.

Lalu lakukan juga pada simpul ke-1.

Kok itu dua kali sih? Karena angka 7 itu lebih kecil dari 14 dan 11, tetapi tidak lebih kecil dari 3. Maka dari itu dipindah posisikan sebanyak dua kali. Dan hasilnya adalah sebagai berikut

Dari data max heap tersebut. Barulah dapat kita lakukan pengurutan data heap dengan syarat :

1. Binary Tree dalam keadaan Max Heap, lalu
2. Hapus atau "Pecat" root dan tukarkan dengan simpul pada posisi terakhir.
3. Banyaknya simpul dikurangi 1
4. Jika n lebih dari 1, maka lakukan reorganisasi heap
5. Lakukan langkah ke-2 hingga ke-5 sampai n = 0.

Dapat dilihat dari ilustrasi dibawah ini.

Karena datanya Binary Tree tidak dalam keadaan Max Heap, maka harus dilakukan lagi pembentukan heap agar menjadi max Heap. Lakukan terus hingga n = 0. Sehingga hasilnya dapat dilihat sebagai berikut.

Dan, waalaa hasil heap sort sudah selesai.

Jika ada pertanyaan bisa langsung tulis di kolom komentar.

Terima Kasih!!!

Sumber :

http://loserbombti.blogspot.co.id/2014/07/algoritma-heap-sort.html
http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L13-HeapSortEx.htm