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 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.
Suatu
heap tree adalah Complete Binary Tree (CBT) di mana harga-harga key pada
node-nodenya sedemikian rupa sehingga haga-harga key pada node-node anaknya
tidak ada yang lebih besar dari harga key pada node orang tuanya.
Heap tree terbagi menjadi 2 jenis yaitu Max-Heap dan Min-Heap,
dimana max-heap adalah kondisi heap tree yang memiliki nilai tertinggi berada
di node root dan setiap child node memiliki nilai yang lebih kecil dari nilai
yang dimiliki parent nodenya. Sedangkan pada min-heap adalah kondisi kebalikan
dengan max-heap, pada min-heap nilai terkecil berada di node root dan setiap
child node memiliki nilai yang lebih besar dari nilai yang dimiliki parent
nodenya. Pada metode heap sort jenis heap tree yang digunakan adalah Max-Heap.
Dan untuk memvisualisasikan sebuah array menjadi
sebuah heap tree adalah dengan cara mencari node root terlebih dahulu yaitu
node pertama node pertama sebuah heap tree adalah index pertama di array yaitu
index 0 akan tetapi pada heap tree node awal berada di posisi 1 berbeda dengan
array yang memiliki index awal yaitu index 0. Setelah node root telah ditemukan
maka sekarang tinggal mencari child node dari node root dan child node terbagi
menjadi 2 yaitu left child dan right child dan untuk mencari left child, right
child, dan parent digunakan rumus sebagai berikut :
Left Child :
2i (Contoh : Left child dari 1 adalah 2 x 1 = 2)
Right Child :
2i + 1 (Contoh : Right Child dari 1 adalah (2 x 1) + 1 = 3
Parent :
└ i/2 ┘ (Contoh : Parent dari 3 adalah 3 / 2 = 1 )
Algoritma
Pengurutan(Sorting Algorithm) Heap Sort
Beberapa metoda sebagai
berikut:
a. Metoda
untuk menginisialisasi suatu CBT (Complete
Binary Tree) a secara umum menjadi
heap tree.
b. Metoda
untuk mengambil data paling besar, yaitu
root dari heap tree.
c. Metoda untuk menambahkan satu key baru
ke dalam heap tree.
d. Metoda untuk menyusun ulang menjadi heap
tree kembali setelah dilakukan metoda b atau c
Algoritma
pengurutan ini mengurutkan isi suatu array masukan dengan memandang array yang
dimasukkan sebagai suatu Complete Binary Tree (CBT). Dengan metoda a maka Complete Binary Tree (CBT) ini
dapat dikonversi menjadi suatu heap tree. Setelah Complete Binary Tree (CBT)
berubah menjadi suatu priority queue, maka dengan mengambil data root satu demi
satu dan disertai dengan metoda d,
key-key dari data root yang kita ambil secara berturutan itu akan terurut
dengan output hasil pengurutan akan dituliskan dalam array hasil dari arah
kanan ke kiri.
Untuk
optimasi memori, kita dapat menggunakan hanya satu array saja. Yaitu dengan
cara memodifikasi metoda b untuk menukar isi root dengan elemen terakhir dalam
heap tree. Jika memori tidak menjadi masalah maka dapat tetap menggunakan 2
array yaitu array masukan dan array hasil.
|
Ide
pertama yang harus kita pikirkan untuk melakukan operasi heapify adalah dari
bagian mana kita harus memulai. Bila kita mencoba dari heapify dari root maka
akan terjadi operasi runut-naik seperti algoritma bubble sort yang akan
menyebabkan kompleksitas waktu yang ada akan berlipat ganda. Setelah diuji,
dengan berbagai hasil maka ide yang efisien adalah membentuk heap tree - heap
tree mulai dari subtree-subtree yang paling bawah. Jika subtree-subtree suatu
node sudah membentuk heap maka tree dari node tersebut mudah dijadikan heap
tree dengan mengalirkannya ke bawah. Jadi, algoritma utama heapify adalah
melakukan iterasi mulai dari internal node paling kanan-bawah (atau berindeks
array paling besar) hingga root, kemudian ke arah kiri dan naik ke level di
atasnya, dan seterusnya hingga mencapai root (sebagai array [0..N-1] ). Oleh
karena itu, iterasi dilakukan mulai dari j = N/2 dan berkurang satu-satu hingga
mencapai j = 0. Pada internal node tersebut, pemeriksaan hanya dilakukan pada
node anaknya langsung (tidak pada level-level lain di bawahnya). Di samping
itu, pada saat iterasi berada di level yang lebih tinggi, subtreesubtreenya
selalu sudah membentuk heap. Jadi, kemungkinan yang paling buruk adalah
restrukturisasi hanya akan mengalirkan node tersebut ke arah bawah. Dengan
demikian, algoritma metoda heapify ini melakukan sebanyak N/2 kali iterasi, dan
pada setiap interasi paling buruk akan melakukan pertukaran sebanyak log2 (N)
kali.
2.
Algoritma Metoda Remove Algoritma metoda
remove hanya menukarkan elemen array pertama dengan elemen array terakhir yang
terdapat di dalam heap tree. Secara logika, node yang berada paling kanan-bawah
dipindahkan ke root untuk menggantikan node root yang akan diambil.
3.
Algoritma Metoda Reheapify Algoritma
metoda reheapify melakukan restrukturisasi dari atas ke bawah seperti halnya
iterasi terakhir dari algoritma metoda heapify. Perbedaan antara metoda heapify
dengan metoda reheapify terletak pada iterasi yang dilakukan oleh kedua
algoritma tersebut. Algoritma metoda reheapify hanya melakukan iterasi terakhir
dari algoritma metoda heapify. Hal ini disebabkan baik subtree kiri maupun
subtree kanannya sudah merupakan heap, sehingga tidak perlu dilakukan iterasi
yang lengkap seperti algoritma metoda heapify. Dan setelah reheapify maka node
yang akan diiterasikan berikutnya akan berkurang satu.
Pseudocode
Algoritma Heap Sorting
HeapSort(A)
Deklarasi array A
Deklarasi Elemen
Input elemen array A
Input nilai-nilai elemen array A
Build-Max-Heap(A)
For i = Elemen – 1 selama i > 0
Tukar A[i] dengan A[0]
Elemen – 1
Max-Heapfy(A, 1)
End for
Build-Max-Heap(A)
For i = (Elemen - 1) / 2 selama i ≥ 0
Max-Heapfy(A, i)
End for
Max-Heapfy(A, i)
Deklarasi left = (i + 1) * 2 – 1
Deklarasi right = (i + 1) * 2
Deklarasi largest
if(left < elemen dan A[left] > A[i])
largest = left
end if
else
largest = i
end else
if(right < elemen dan A[right] > A[i])
largest = right
. end if
if(largest != i)
Tukar A[i] dengan A[largest]
Max-Heapfy(A, i)
end if
untuk contoh soal penerapan bisa kalian cari sendiri .terima kasih
