Algoritma : Heapsort
Definisi Heap Sort
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. Atau dilakukan dengan cara membangun struktur data
heap dan kemudian menerapkan langkah menghapus node heap. Pada awalnya, kondisi
heap kosong. Kemudian, node heap di-insert satu per satu. Cara alternatif
adalah, menampung data yang akan diurutkan dalam array, kemudian node pada
bagian root di hapus. Jika heap adalah minimal heap, maka data pada root adalah
data terkecil, terdapat 2 contoh heap yaitu MAXHEAP (nilai orangtua ≥ nilai
anaknya) MIN HEAP (nilai orangtua ≤ nilai anaknya).
Algoritma Heap Sort
|
|
Pseudocode:
|
|
Judul:
program_heap_sort
|
|
Deklarasi:
|
if (largest != i)
{
|
Integer= A[100], i, length, le, ri, heapsize, largest
|
exchange A[i]
<-> A[largest]
|
Deskripsi:
|
Heapify(A,
largest)
|
Heapsort(A) {
|
}
|
BuildHeap(A)
|
}
|
for i <-
length(A) downto 2 {
|
|
exchange A[1]
<-> A[i]
|
|
heapsize <-
heapsize -1
|
|
Heapify(A, 1)
|
|
}
|
|
BuildHeap(A) {
|
|
heapsize <-
length(A)
|
|
for i <-
floor( length/2 ) downto 1
|
|
Heapify(A, i)
|
|
}
|
|
Heapify(A, i) {
|
|
le <- left(i)
|
|
ri <- right(i)
|
|
if (le<=heapsize)
and (A[le]>A[i])
|
|
largest <-
le
|
|
else
|
|
largest <-
i
|
|
if
(ri<=heapsize) and (A[ri]>A[largest])
|
|
largest <-
ri
|
Contoh Kasus Heap Sort
A[5]=1,4,5,3,2 = integer
Buatlah array A[5] dalam MAX HEAP Tree!
Solusi
:
Pada
gambar 1, angka 1 merupakan orangtua dan angka 4 merupakan anaknya. Pada heap
tree max heap, nilai orangtua ≥ nilai
anaknya. Karena pada gambar 1 nilai orangtua < nilai anaknya maka nilai
orangtua dengan nilai anaknya di tukar. Sehingga heap tree pada gambar 1 berubah
menjadi heap tree pada gambar 2.
Pada
gambar 2, angka 4 merupakan orangtua dan angka 5 merupakan anaknya. Pada heap
tree max heap, nilai orangtua ≥ nilai
anaknya. Karena pada gambar 2 nilai orangtua < nilai anaknya maka nilai
orangtua dengan nilai anaknya di tukar. Sehingga heap tree pada gambar 2
berubah menjadi heap tree pada gambar 3.
Pada
gambar 3, angka 1 merupakan orangtua dan angka 3 merupakan anaknya. Pada heap
tree max heap, nilai orangtua ≥ nilai
anaknya. Karena pada gambar 3 nilai orangtua < nilai anaknya maka nilai
orangtua dengan nilai anaknya di tukar. Sehingga heap tree pada gambar 3
berubah menjadi heap tree pada gambar 4.
Pada
gambar 4, angka 3 merupakan orangtua dan angka 2 merupakan anaknya. Pada heap
tree max heap, nilai orangtua ≥ nilai
anaknya. Karena pada gambar 4 nilai orangtua ≥ nilai anaknya maka nilai
orangtua dengan nilai anaknya tidak di tukar. Sehingga heap tree pada gambar 4
tidak berubah (gambar 5).
0 komentar: