Pendahuluan
Untuk
memecahkan masalah pengurutan dalam membangun suatu program aplikasi,
dibutuhkan algoritma pengurutan. Di dalam bidang Teknik Informatika
terdapat banyak sekali jenis-jenis algoritma pengurutan yang dapat
digunakan untuk memecahkan masalah pengurutan.
Pengurutan
data (data sorting) merupakan bagian dari pengolahan data informasi.
Dari data-data yang telah didapat, ada kalanya data tersebut harus
diurutkan terlebih dahulu berdasarkan aturan yang lebih dulu ditentukan.
Berdasarkan nilai maupun alphabet misalnya.
Metode-metode
pengurutan data pun ada berbagai jenis. Mulai dari binary sort,
insertion sort, merge sort, heap sort dll. Penggunaan metode mana yang
akan dipakai nantinya tergantung dari jenis maupun kuantitas data yang
diolah.
Heap sort, algoritma
pengurutan, merupakan salah satu metode pengurutan yang sering
digunakan. Melalui jurnal ini akan dibahas teknik pencarian ini beserta
kelebihan dan kekurangannya.
Oleh
karena itu, teknik untuk memilih algoritma pengurutan yang tepat,
sesuai dengan kebutuhan, dan mangkus sangat diperlukan karena
masing-masing algoritma pengurutan memiliki karakteristik yang
berbedabeda. Heap sort merupakan salah satu contoh algoritma pengurutan
yang memiliki kompleksitas waktu asimptotik terbaik serta menerapkan
teknik yang unik/khas di dalam memecahkan masalah pengurutan, yaitu
dengan menggunakan heap tree.
Heap
Pengertian Heap
Pohon
heap adalah struktur data yang berbentuk pohon yang memenuhi
sifat-sifat heap yaitu jika B adalah anak dari A, maka nilai yang
tersimpan di simpul A lebih besar atau sama dengan nilai yang tersimpan
di simpul B. Hal ini mengakibatkan elemen dengan nilai terbesar selalu
berada pada posisi akar, dan heap ini disebut max heap. (Bila
perbandingannya diterbalikkan yaitu elemen terkecilnya selalu berada di
simpul akar, heap ini disebut adalah min heap). Karena itulah, heap
biasa dipakai untuk mengimplementasikan priority queue. Operasi-operasi
yang digunakan untuk heap adalah :
• Delete-max atau delete-min: menghapus simpul akar dari sebuah max- atau minheap.
• Increase-key atau decrease-key : mengubah nilai yang tersimpan di suatu simpul.
• Insert: menambahkan sebuah nilai ke dalam heap.
• Merge: menggabungkan dua heap untuk membentuk sebuah heap baru yang berisi semua elemen pembentuk heap tersebut.
Gambar : Contoh dari max heap
Jenis-jenis Heap :
- Binary heap : Binary heap adalah heap yang dibuat dengan menggunakan pohon biner.
- Binomial heap
: Binomial heap adalah heap yang dibuat dengan menggunakan pohon
binomial. Pohon binomial bila didefinisikan secara rekursif adalah:
- Sebuah pohon binomial dengan tinggi 0 adalah simpul tunggal
- Sebuah
pohon binomial dengan tinggi k mempunyai sebuah simpul akar yang
anak-anaknya adalah akar-akar pohonpohon binomial dengan tinggi k-1,k-
2,…,2,1,0.
Gambar : pohon-pohon binomial dengan tinggi (order) 0 s/d 3
3.
Fibonacci Heap
Fibonacci
heap adalah kumpulan pohon yang membentuk minimum heap. Pohon dalam
struktur data ini tidak memiliki bentuk yang tertentu dan pada kasus
yang ekstrim heap ini memiliki semua elemen dalam pohon yang berbeda
atau sebuah pohon tunggal dengan tinggi n. Keunggulan dari Fibonacci
heap adalah ketika menggabungkan heap cukup dengan menggabungkan dua
list pohon.
Gambar : Contoh Fibonacci heap
Perbandingan kompleksitas jenis-jenis heap
Tabel 1. Perbandingan macam-macam heap
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 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.
1. Algoritma Heapify
Algoritma
Heapify adalah membangun sebuah heap dari bawah ke atas, secara
berturut-turut berubah ke bawah untuk membangun heap. Permasalahan
pertama yang harus kita pertimbangkan dalam melakukan operasi heapify
adalah dari bagian mana kita harus memulai. Bila kita mencoba operasi
heapify dari akar maka akan terjadi operasi runut-naik seperti algoritma
bubble sort yang akan menyebabkan kompleksitas waktu yang ada akan
berlipat ganda. Sebuah versi lain adalah membangun heap secara
atas-bawah dan berganti-ganti ke atas untuk secara konseptual lebih
sederhana untuk ditangani. Versi ini mulai dengan sebuah heap kosong dan
secara berturut-turut memasukkan data. Versi lainnya lagi adalah dengan
membentuk pohon heap-pohon heap mulai dari subtree-subtree yang paling
bawah. Jika subtree-subtree suatu simpul sudah membentuk heap maka pohon
dari simpul tersebut mudah dijadikan pohon heap dengan mengalirkannya
ke bawah. Setelah diuji, maka ide yang paling efisien adalah versi yang
terakhir, yang kompleksitas algoritmanya pada kasus terburuk adalah
O(n), sedangkan versi membentuk heap tree-heap tree dari atas ke bawah
kompleksitas nya O(n log n).
Jadi,
algoritma utama heapify adalah melakukan iterasi mulai dari internal
simpul paling kanan bawah(pada representasi larik, adalah elemen yang
berada di indeks paling besar) hingga akar, kemudian kearah kiri dan
naik ke level di atasnya, dan seterusnya hingga mencapai akar (sebagai
larik [0..N-1]). Oleh karena itu, iterasi dilakukan mulai dari j= N/2
dan berkurang satu-satu hingga mencapai j=0. Pada simpul internal
tersebut, pemeriksaan hanya dilakukan pada simpul anaknya langsung
(tidak pada level-level lain di bawahnya). Pada saat iterasi berada di
level yang lebih tinggi, subtreesubtree selalu sudah membentuk heap.
Jadi, kasus yang paling buruk adalah restrukturisasi hanya akan
mengalirkan simpul tersebut kearah bawah. Dengan demikian, heapify versi
ini melakukan sebanyak N/2 kali iterasi, dan pada kasus yang paling
buruk akan melakukan iterasi sebanyak ²log(N) kali.
2. Algoritma Remove
Algoritma
remove ini menukar akar (yang berisi nilai maksimum) dari heap dengan
elemen terakhir. Secara logika, simpul yang berada paling kanabawah
dipindahkan ke akar untuk menggantikan simpul akar yang akan diambil.
3. Algoritma Reheapify
Algoritma
reheapify ini melakukan pembuatan ulang heap dari atas ke bawah seperti
halnya iterasi terakhir dari algoritma metoda heapify. Perbedaan antara
metode heapify dengan metode reheapify ada pada iterasi yang dilakukan
oleh kedua algoritma tersebut. Algoritma metode reheapify ini hanya
melakukan iterasi terakhir dari algoritma heapify. Hal ini disebabkan
baik subtree kiri maupun subtree kanannya sudah merupakan heap, sehingga
tidak perlu dilakukan iterasi lengkap seperti algoritma heapify. Dan
setelah reheapify maka simpul yang akan diiterasikan berikutnya akan
berkurang satu.
Penerapan Algoritma Pengurutan Heap Sort
Salah
satu contoh penerapan algoritma pengurutan (sorting algorithm) heap
sort adalah sebagai berikut: Misalkan terdapat suatu array bilangan
bulat yang terdiri dari sepuluh buah anggota dengan nilai data 11, 9, 8,
27, 16, 25, 12, 13, 34, dan 43. Kita akan mengurutkan data diatas
dengan menggunakan heapsort. Pertama-tama, array di atas dapat dipandang
sebagai suatu Complete Binary Tree (CBT) sebagai berikut:
Selanjutnya
algoritma metoda heapify dilakukan dengan iterasi dari subtree node
ke-4, ke-3, dan seterusnya berturut-turut hingga mencapai root (akar).
Iterasi dilakukan mulai dari node ke-4 karena N/2 dalam contoh di atas
adalah 5. Dan elemen kelima dari array memiliki nilai indeks 4 sebab
indeks array biasanya diawali dari 0. Penerapan algoritma metoda heapify
terhadap Complete Binary Tree (CBT) pada contoh di atas menghasilkan
operasi-operasi pertukaran sebagai berikut:
1. Subtree node ke-4: pertukaran 16 dengan 43
2. Subtree node ke-3: pertukaran 27 dengan 34
3. Subtree node ke-2: pertukaran 8 dengan 25
4. Subtree node ke-1: pertukaran 9 dengan 43, lalu pertukaran 9 dengan 16
5.
Subtree node ke-0: pertukaran 11 dengan 43, lalu pertukaran 11 dengan
34, serta akhirnya pertukaran 11 dengan 27 Perubahan-perubahan
(pertukaran) tersebut dapat digambarkan sebagai berikut:
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 43 di-remove dan 9 menggantikan posisi yang ditinggalkan oleh
43, maka terjadi reheapify: penukaran 9 dengan 34, 9 dengan 27, dan 9
dengan 13.
dan data yang telah terurut adalah 43.
2.
Setelah 34 di-remove dan 11 menggantikan posisi yang ditinggalkan oleh
34, maka terjadi reheapify: penukaran 11 dengan 27, dan 11 dengan 16.
dan data yang telah terurut adalah 34, 43.
3.
Setelah 27 di-remove dan 9 menggantikan posisi yang ditinggalkan oleh
27, maka terjadi reheapify: penukaran 9 dengan 25, dan 9 dengan 12.
dan data yang telah terurut adalah 27, 34, 43.
4.
Demikian seterusnya dilakukan algoritma metoda remove dan algoritma
metoda reheapify hingga tidak ada lagi node yang tersisa. Dan pada
akhirnya akan didapatkan hasil data yang telah terurut adalah 8, 9, 11,
12, 13, 16, 25, 27, 34, 43.
Program Heap Sort & Penjelasannya
<#include <>
void restoreHup(int*,int); // pemanggilan fungsi void restoreHup
void restoreHdown(int*,int,int); //pemanggilan fungsi void restoreHdown
void main()
{ // pembuka void main
int a[20],n,i,j,k; // mendeklarasikan bahwa a[20] ,n,i,j,k adalah integer
printf(" Masukkan jumlah element : ");// untuk menampilkan kelayar perintah memasukkan jumlah element
scanf("%d",&n); // untuk mengidentifikasikan nilai yang dimasukkan melalui keyboard
printf(" Masukkan element : "); //untuk menampilkan kelayar perintah untuk memasukkan element
for(i=1;i<=n;i++) //funsi for dimana jika ketentuan untuk i terpenuhi maka progran di bawahnya akan dijalankan
{ // pembuka fungsi for
scanf("%d",&a[i]); // untuk mengidentifikasi array a
restoreHup(a,i); // a , i dalam fungsi restoreHup
} // penutup fungsi for
j=n; // nilai j sama dengan n
for(i=1;i<=j;i++) //funsi for dimana jika ketentuan untuk i terpenuhi maka progran di bawahnya akan dijalankan
{ // pembuka fungsi for
int temp; // temp sebagai integer
temp=a[1]; // temp sama dengan nilai array a yang pertama
a[1]=a[n]; // nilai array a yg ke 1 sama dengan array a yang ke n
a[n]=temp; // nilai array a yang ke n sama dengan nilay temp
n--; // nilai n selalu berkurang 1
restoreHdown(a,1,n); // a , 1, n dalam fungsi restoreHdown
} // penutup fungsi for
n=j; // n sama dengan nilai j
printf(" Here is it... "); // untuk menampilkan perintah ke dalam layar
for(i=1;i<=n;i++) //funsi for dimana jika ketentuan untuk i terpenuhi maka progran di bawahnya akan dijalankan
printf("%4d",a[i]); // untuk menampilkan nilai array ke i ke layar
} // penutup void main
void restoreHup(int *a,int i) // fungsi void restore Hup
{ // pembuka fungsi foid restoreHup
int v=a[i]; // v sama dengan nilai array a yang ke i
while((i>1)&&(a[i/2]
{ // pembuka fungsi while
a[i]=a[i/2]; // nilai array a yang ke i sama dengan nilai array a yang ke i/2
i=i/2; // nilai i sama dengan nilai i/2
} //penutup fungsi while
a[i]=v; // nilai array a yang ke i sama dengan nilai v
} // penutup fungsi while
void restoreHdown(int *a,int i,int n) // fungsi void restoreHdown
{ // pembuka fungsi void restoreHdown
int v=a[i]; // v sama dengan nilai array a yang ke i sebagai integer
int j=i*2;// nilai j sama dengan i kali 2 ialah integer
while(j<=n) // fungsi while akan dijalankan bila ketentuannya terpenuhi
{ // pembuka fungsi while
if((j
j++; // nilai j akan selalu tambah 1
if(a[j]
break;
a[j/2]=a[j]; // nilai array a yang ke j/2 sama dengan nilai array a yang ke j
j=j*2; // nilai j sama dengan nilai j*2
}// penutup fungsi while
a[j/2]=v;// nilai array a yang ke j/2 sama dengan v
}// penutup fungsi void restorehdown
//Suatu program untuk mengimplementasikan Heap Sort>
Hasil Program diatas :
Kesimpulan
-
Algoritma pengurutan heap sort dapat digunakan untuk menyelesaikan
masalah-masalah pengurutan dalam membangun suatu program aplikasi dengan
mangkus.
- Keunggulan algoritma pengurutan heap sort terletak pada kompleksitas waktu asimptotiknya yang sangat baik.
-
Meskipun lebih lambat dari algoritma pengurutan data yang lain,
algoritma heap sort memiliki kelebihan ketika menangani data dalam skala
yang besar/massive. Karena algoritma ini memiliki kelebihan tidak
menggunakan banyak tabel, tetapi hanya satu tabel yang dipakai untuk
menyimpan hasil dari pengurutan tersebut.
Referensi / Daftar Pustaka
- www.google.com
- http://www.informatika.org/~rinaldi/Matdis/2008-2009/Makalah2008/Makalah0809-046.pdf
- http://www.informatika.org/~rinaldi/Stmik/Makalah/MakalahStmik08.pdf
- http://www.ilmu-komputer.net/algorithms/heap-sort-source-code/
- http://algoritmapemrogaman.blogspot.com/2010/02/jurnal-heap.html
1.
