Algoritma HeapSort

Definisi
Heap Sort adalah sebuah algoritma pengurutan yang paling lambat dari algoritma yang memiliki kompleksitas O(n log n). Tetapi tidak seperti algoritma Merge Sort dan Quick Sort, algoritma Heap Sort tidak memerlukan rekursif yang besar atau menggunakan banyak tabel (array). Oleh karena itu, Heap Sort adalah pilihan yang baik untuk sebuah kumpulan data yang besar.
Algoritma ini bekerja dengan menentukan elemen terbesar (atau terkecil) dari sebuah daftar elemen, dan diletakkan pada akhir (atau awal) dari daftar tersebut. Heap sort menyelesaikan sebuah pengurutan menggunakan struktur data yang disebut heap.
Algoritma ini dimulai dengan membangun sebuah array heap dengan membangun tumpukan dari kumpulan data, lalu memindahkan data terbesar ke bagian belakang dari sebuah tabel hasil. Setelah itu, array heap dibangun kembali, kemudian mengambil elemen terbesar untuk diletakkan di sebelah item yang telah dipindahkan tadi. Hal ini diulang sampai array heap habis.
Jadi secara umum, algoritma ini memerlukan dua buah tabel; satu tabel untuk menyimpan heap, dan satu tabel lainnya untuk menyimpan hasil. Walaupun lebih lambat dari Merge Sort atau Quick Sort, algoritma ini cocok untuk digunakan pada data yang berukuran besar.


PSEUDOCODE

function heapsort(a, count) {
var int start := count ÷ 2 – 1
end := count – 1
while start ≥ 0
sift(a. start, count)
start := - 1
while end > 0
swap(a[end], a[0])
sift(a, 0, end)
end := end – 1
}
function sift(a. start, count) {
var int root := start, child
while root * 2 + 1 < count {
child := root * 2 + 1
if child < count – 1 and
a[child] < a[child +]
child := child + 1
if a[root]> a[child]
swap([root],  a[child])
root := child
else
return
}
}

Contoh
Terdapat sebuah array bilangan bulat yang terdiri atas 5 buah anggota dengan nilai data 5, 3, 1, 9, 8. Urutkan data di atas secara ascending dengan menggunakan metode heap sort.
Jawab:
1.    Pertama, umpamakan array tersebut sebagai suatu CBT (Complete Binary Tree), yaitu

 

2.    Selanjutnya algoritma metoda heapify dilakukan dengan iterasi dari subtree node ke-2 sampai ke akar. Pada Complete Binary Tree di atas menghasilkan operasi-operasi pertukaran sebagai berikut:
i.    Subtree node ke-2: pertukaran 3 dengan 8
ii.    Subtree node ke-1: pertukaran 8 dengan 9
iii.    Subtree node ke-0: pertukaran 5 dengan 9


 







Semua perubahan di atas terjadi dalam array yang bersangkutan, sehingga pada akhirnya diperoleh tree terakhir yang merupakan heap tree. Sementara itu, dalam iterasi yang melakukan/menerapkan algoritma metoda remove( ) dan algoritma metoda reheapify() akan terjadi pemrosesan berikut:

1.    Setelah 9 di-remove, dan 3 menggantikan posisi yang ditinggalkan oleh 9, maka selanjutnya terjadi reheapify: penukaran 3 dengan 5, 3 dengan 8, dan 5 dengan 8. Sementara, data yang telah terurut adalah 9.





2.    Selanjutnya 8 di-remove, lalu 3 menggantikan posisi yang ditinggalkan oleh 8, dan selanjutnya terjadi reheapify: penukaran 3 dengan 5. Data yang telah terurut adalah 8, 9.



3.    Selanjutnya 5 di-remove, lalu 1 menggantikan posisi yang ditinggalkan oleh 5, dan selanjutnya terjadi reheapify: penukaran 1 dengan 3. Data yang telah terurut adalah 5, 8, 9.



4.    Selanjutnya 3 di-remove dan 1 menggantikan posisi 3. Karena node yang tersisa hanya 1, maka tidak terjadi reheapify. Data yang telah terurut adalah 3, 5, 8, 9.
5.    Langkah terakhir adalah 1 di-remove, dengan demikian tidak ada lagi node yang tersisa, sehingga seluruh data telah terurut yaitu 1, 3, 5, 8, 9.

Sekian Postingan kali ini. Semoga bermanfaat.