Dalam dunia pemrograman Algoritma Sorting sangat
diperlukan untuk mengatasi masalah-masalah yang berkenaan dengan pengurutan
data. Sorting adalah proses menyusun elemen – elemen dengan tata
urut tertentu dan proses tersebut terimplementasi dalam bermacam-macam
aplikasi.
Heap Sort
Heapsort adalah metode mengurutkan dengan memanfaatkan
sifat yang dimiliki oleh struktur data heap. Heap
bekerja dengan menentukan elemen terbesar atau terkecil dari sebuah daftar
elemen, dan diletakkan pada akhir atau awal dari daftar tersebut. Heap
sendiri adalah sebuah “Binary Search Tree” atau struktur
data berbentuk pohon yang memenuhi sifat-sifat heap yaitu jika B adalah anak
dari A (parent), maka nilai yang tersimpan di simpul A (parent) lebih besar atau
sama dengan nilai yang tersimpan di simpul B.
elemen dengan nilai terbesar akan berada pada
posisi akar, disebut max heap, sedangkan elemen terkecilnya akan berada di
simpul akar, disebut min heap. Untuk mendapatkan nilai max-heap,
dibutuhkan sebuah prosedur yang dinamakan MAX-HEAPIFY dengan input array A dan
indeks i pada array tersebut.
MAX-HEAPIFY mengasumsikan pohon biner yang memiliki cabang kiri dan
kanan; dan memiliki parent berupa max heap, tetapi sebuah array A[i]
mungkin bernilai lebih kecil dari anaknya. Prosedur MAX-HEAPIFY
menghasilkan semua nilai array A[i] selalu di bawah max-heap sehingga
semua subtree yang berakar pada indeks i memenuhi sifat max-heap.
Prosedur MAX-HEAPIFY digunakan untuk mengkonversi array
A[1…n] menjadi max heap dimana n adalah A.length. Sedangkan prosedur
BUILD-MAX-HEAP melewati semua node pada tree, kemudian menjalankan MAX-HEAPIFY
satu per satu.
Operasi-operasi yang digunakan untuk heap antaralain :
• 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.
Daftar algoritma untuk heap sort :
function heapSort(a, count) is
input: sebuah larik tidak terurut a dengan panjang length
(pertama letakkan a dalam max-heap) heapify(a, count)
end := count -1
while end > 0 do
remove ( )
reheapify ( )
end := end – 1
Contoh sourcode implementasi Heapsort dalam java:
<!DOCTYPE html>
<html>
<title>Program Pengurutan menggunakan Metode Heapsort</title>
<body>
<?php
function build_heap(&$array, $i, $t){
$tmp_var = $array[$i];
$j = $i * 2 + 1;
while ($j <= $t){
if($j < $t){
if($array[$j] < $array[$j + 1]){
$j = $j + 1;
}
}
if($tmp_var < $array[$j]){
$array[$i] = $array[$j];
$i = $j;
$j = 2 * $i + 1;
} else {
$j = $t + 1;
}
}
$array[$i] = $tmp_var;
}
function heap_sort(&$array){
$init = (int)floor((count($array)-1) / 2);
for($i = $init; $i >= 0; $i--){
$count = count($array) - 1;
build_heap($array, $i, $count);
}
for($i = (count($array) - 1); $i >= 1; $i--){
$tmp_var = $array[0];
$array [0] = $array [$i];
$array [$i] = $tmp_var;
build_heap($array, 0, $i - 1);
}
}
$array = array();
echo '<h3>Element Array Sebelum Terurut :</h3>';
for($p = 0; $p <= 49; $p++){
$array[$p] = rand(10,99);
}
for($i = 0; $i <= count($array)-1; $i++){
if($i%10 == 0) echo '<br />';
echo $array[$i].' ';
}
echo '<br /><br />';
echo '<h3>Element Array Setelah Terurut (Heap Sort):</h3>';
heap_sort($array);
for($i = 0; $i <= count($array)-1; $i++){
if($i%10 == 0) echo '<br />';
echo $array[$i].' ';
}
?>
</body>
</html>
Hasil :
