Pengertian Heap Shorting
Heap Shorting adalah sebuah metode sorting (pengurutan) angka pada sebuah array dengan cara menyerupai binary tree , yaitu dengan cara menyajikan sebuah array menjadi sebuah binary tree yang nantinya pada binary tree tersebut nilai pada masing-masing index array akan diurutkan. Algoritma ini bekerja dengan menentukan elemen terbesar (atau terkecil) dari keseluruhan daftar elemen yang ada dan menentukan posisi dari elemen yang telah ditentukannya apakah pada akhir (atau awal) dari daftar elemen tersebut.
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 lebih kecil dibandingkan dengan parent nodenya. Sedangkan min-heap adalah kondisi kebalikan dari max-heap, dimana nilai terkecil berada pada node root dan setiap child node memiliki nilai lebih besar dari pada parent nodenya.
Algoritma Pada Heap Shorting
Dalam heap shorting terdapat dua metode yang digunakan yaitu Build-Max-Heap dan Max-Heapfy, Build-Max-Heap adalah metode yang digunakan untuk membuat heap tree memenuhi kondisi max-heap, berikut adalah algoritma dari metode HeapSort, Build-Max-Heap, dan Max-Heapfy pada sebuah heap tree :
HeapSort(A)
1. Deklarasi array A
2. Deklarasi Elemen
3. Input elemen array A
4. Input nilai-nilai elemen array A
5. Build-Max-Heap(A)
6. For i = Elemen – 1 selama i > 0
7. Tukar A[i] dengan A[0]
8. Elemen – 1
9. Max-Heapfy(A, 1)
10. End for
Dapat dilihat pada algoritma HeapSort terdapat dua metode yang dipanggil yaitu Build-Max-Heap dan Max-Heapfy, dan algoritma dari Build-Max-Heap adalah:
Build-Max-Heap(A)
1. For i = (Elemen - 1) / 2 selama i ≥ 0
2. Max-Heapfy(A, i)
3. End for
Pada metode Build-Max-Heap terdapat for looping yang membagi 2 jumlah elemen, disini elemen ke 1 karena pada array index awal adalah 0 sedangkan pada heap tree adalah 1, lalu elemen dibagi 2 dan selama i ≥ 0 maka for looping akan terus berajalan. Dan berikut adalah metode Max-Heapfy :
Max-Heapfy(A, i)
1. Deklarasi left = (i + 1) * 2 – 1
2. Deklarasi right = (i + 1) * 2
3. Deklarasi largest
4. if(left < elemen dan A[left] > A[i])
5. largest = left
6. end if
7. else
8. largest = i
9. end else
10. if(right < elemen dan A[right] > A[i])
11. largest = right
12. end if
13. if(largest != i)
14. Tukar A[i] dengan A[largest]
15. Max-Heapfy(A, i)
16. end if
Sebenarnya metode Max-Heapfy digunakan untuk mengoreksi posisi dari index yang dipilih apakah posisinya sudah memenuhi kondisi Max-Heap yaitu tiap node parent harus memiliki nilai lebih tinggi dari nilai yang dimiliki child nodenya, dan dengan metode Max-Heapfy pengaturan posisi node yang memenuhi kondisi Max-Heap dapat dilakukan.
Contoh Penerapan Metode Heap Shorting
Sebagai contoh, akan dimasukkan 5 bilangan acak dan akan diurutkan menggunakan heap sort dari bilangan terkecil ke bilangan terbesar. Lima bilangan acak tersebut adalah 7, 5, 4, 3, 6. Langkah pertama yang dilakukan adalah tempatkan bilangan-bilangan tersebut ke bentuk heap tree dengan tetap memperhatikan indexnya.
Heap Shorting adalah sebuah metode sorting (pengurutan) angka pada sebuah array dengan cara menyerupai binary tree , yaitu dengan cara menyajikan sebuah array menjadi sebuah binary tree yang nantinya pada binary tree tersebut nilai pada masing-masing index array akan diurutkan. Algoritma ini bekerja dengan menentukan elemen terbesar (atau terkecil) dari keseluruhan daftar elemen yang ada dan menentukan posisi dari elemen yang telah ditentukannya apakah pada akhir (atau awal) dari daftar elemen tersebut.
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 lebih kecil dibandingkan dengan parent nodenya. Sedangkan min-heap adalah kondisi kebalikan dari max-heap, dimana nilai terkecil berada pada node root dan setiap child node memiliki nilai lebih besar dari pada parent nodenya.
Algoritma Pada Heap Shorting
Dalam heap shorting terdapat dua metode yang digunakan yaitu Build-Max-Heap dan Max-Heapfy, Build-Max-Heap adalah metode yang digunakan untuk membuat heap tree memenuhi kondisi max-heap, berikut adalah algoritma dari metode HeapSort, Build-Max-Heap, dan Max-Heapfy pada sebuah heap tree :
HeapSort(A)
1. Deklarasi array A
2. Deklarasi Elemen
3. Input elemen array A
4. Input nilai-nilai elemen array A
5. Build-Max-Heap(A)
6. For i = Elemen – 1 selama i > 0
7. Tukar A[i] dengan A[0]
8. Elemen – 1
9. Max-Heapfy(A, 1)
10. End for
Dapat dilihat pada algoritma HeapSort terdapat dua metode yang dipanggil yaitu Build-Max-Heap dan Max-Heapfy, dan algoritma dari Build-Max-Heap adalah:
Build-Max-Heap(A)
1. For i = (Elemen - 1) / 2 selama i ≥ 0
2. Max-Heapfy(A, i)
3. End for
Pada metode Build-Max-Heap terdapat for looping yang membagi 2 jumlah elemen, disini elemen ke 1 karena pada array index awal adalah 0 sedangkan pada heap tree adalah 1, lalu elemen dibagi 2 dan selama i ≥ 0 maka for looping akan terus berajalan. Dan berikut adalah metode Max-Heapfy :
Max-Heapfy(A, i)
1. Deklarasi left = (i + 1) * 2 – 1
2. Deklarasi right = (i + 1) * 2
3. Deklarasi largest
4. if(left < elemen dan A[left] > A[i])
5. largest = left
6. end if
7. else
8. largest = i
9. end else
10. if(right < elemen dan A[right] > A[i])
11. largest = right
12. end if
13. if(largest != i)
14. Tukar A[i] dengan A[largest]
15. Max-Heapfy(A, i)
16. end if
Sebenarnya metode Max-Heapfy digunakan untuk mengoreksi posisi dari index yang dipilih apakah posisinya sudah memenuhi kondisi Max-Heap yaitu tiap node parent harus memiliki nilai lebih tinggi dari nilai yang dimiliki child nodenya, dan dengan metode Max-Heapfy pengaturan posisi node yang memenuhi kondisi Max-Heap dapat dilakukan.
Contoh Penerapan Metode Heap Shorting
Sebagai contoh, akan dimasukkan 5 bilangan acak dan akan diurutkan menggunakan heap sort dari bilangan terkecil ke bilangan terbesar. Lima bilangan acak tersebut adalah 7, 5, 4, 3, 6. Langkah pertama yang dilakukan adalah tempatkan bilangan-bilangan tersebut ke bentuk heap tree dengan tetap memperhatikan indexnya.
Sesuai dengan metode Max-Heap dimana nilai dari parent node harus lebih besar dari pada child node, sesuai dengan gambar susunan heap tree tersebut, terlihat bahwa node 5 memiliki nilai lebih besar dari node 3 yang merupakan node parent maka tukar nilai dari kedua node tersebut
Sampai disini proses Build-Max-Heap, karena susunan dari heap tree telah mengikuti aturan max-heap, dimana nilai terbesar berada di node root dan node parent telah memiliki nilai lebih besar dari node child.
Setelah proses Build-Max-Heap selesai, selanjutnya lakukan pengurutan menggunakan metode HeapSort. Pada algoritma heapsort setelah algoritma Build-Max-Heap nilai pada node terakhir akan ditukar dengan node 1 (root) selama nilai node terakhir masi lebih besar daripada 0, disini nilai 7 akan ditukar dengan nilai 5 dan jumlah elemen akan dikurangi satu tetapi setelah pertukaran posisi dilakukan heap tree tidak memenuhi kondisi Max-Heap maka algoritma Max-Heapfy akan digunakan kembali, sebagai berikut.
Sampai pada tahap ini nilai terbesar sudah berada pada posisi yang benar yakni pada node terakhir, langkah selanjutnya adalah mengulang cara yang sama dengan for looping selama nilai node terakhir masi lebih besar dari 0. Berikut merupakan gambaran lengkapnya
Maka setelah algoritma HeapSort dilakukan bilangan-bilangan tersebut akan terurut dari nilai terkecil sampai terbesar. 3, 4, 5, 6, 7.
http://loserbombti.blogspot.co.id/search?q=algoritma+heap+sorting
0 komentar:
Posting Komentar