Heap sort, pengurutan yang sederhana

Oke, lanjut!

Heapsort adalah metode mengurutkan dengan memanfaatkan sifat yang dimiliki oleh struktur data heap. Heap sendiri adalah sebuah “binary search tree” dengan sifat parent memiliki nilai >= nilai yang ada di anaknya. Meski dikatakan ia adalah sebuah binary search tree, namun heap lebih diarahkan ke konsepsi / menganggap suatu array memiliki sifat heap.

Ambil suatu indeks dari array, misal i. Jika dianggap elemen di i sebagai node, ia akan disebut parent jika ia memiliki anak dengan indeks 2i+1 dan 2i+2. Contoh: indeks 0 akan memiliki anak di indeks 1 dan 2.

Heapsort dimulai dengan membentuk array memenuhi sifat heap untuk seluruh indeks. Setelah melakukan penataan, dipastikan elemen terbesar akan berada di root / node paling atas heap (indeks 0). Nah, selanjutnya adalah kita pindahkan elemen terbesar itu ke belakang barisan. Untuk node dari 0 hingga n-2, lakukan penataan lagi dan pemindahan elemen terbesar ke belakang. Hasilnya adalah elemen akan terurut secara ascending setelah proses ini.

Source code dalam C++ dapat teman-teman temukan di sini:

void siftDown(int arr[], int start, int end) {
/** start dan end berada dalam jangkauan array yang terdefinisi dengan start < end **/
/** Menata array dalam jangkauan sesuai kriteria sifat heap **/

/** deklarasi **/
int root=start;        // pencarian dimulai dari root
int child;            // menyimpan indeks anak yang diperiksa
int inswap;            // indeks untuk swap
int temp;

/** sift ketika root masih memiliki anak **/
/** indeks anak ada di 2*root+1 dan 2*root+2 **/
while(2*root+1 <= end) {
child     = 2*root+1;    // dapatkan data anak
inswap     = root;
/** Ambil elemen terbesar dan letakkan di root **/
if(arr[inswap] < arr[child])
inswap = child;
if(child+1 <= end)
if(arr[inswap] < arr[child+1])
inswap = child+1;
if(root!=inswap) {
// pertukarkan
temp         = arr[root];
arr[root]     = arr[inswap];
arr[inswap]    = temp;
// track down, buat agar struktur heap di bawah konsisten
root = inswap;
} else return;
}
}

//————————————————————————————

void heapify(int arr[], int n) {
/** n = jumlah elemen di array **/

    /** heapidy membentuk heap dengan bantuan siftdown. Hasil akhirnya adalah array yang tertata sesuai sifat heap **/

/** mulai heapify dari tengah dan terus naik hingga indeks 0 **/
int start=(n-2)/2;
for(int i=start; i>=0; i–)
siftDown(arr,i,n-1);
}

//————————————————————————————

void heapsort(int arr[], int n) {
/** n = jumlah elemen di array **/

/** lakukan heapify untuk menciptakan heap semu **/
heapify(arr,n);
/** tercipta heap, elemen terbesar ada di root (indeks 0)
*  lakukan iterasi untuk setiap langkah, pindahkan root ke akhir,
*  decrement indeks dan lakukan penataan ulang lagi
*/
int end=n-1;
int temp;
while(end>0) {
// pindahkan root ke akhir
temp     = arr[0];
arr[0]     = arr[end];
arr[end]= temp;
// majukan end
end -= 1;
// lakukan penataan ulang dengan siftDown
siftDown(arr,0,end);
}
}

Ada pertanyaan?