Heap Sort

            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 min heap.

• 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.

Heap Sort

            HeapSort adalah algoritma pengurutan data berdasarkan perbandingan, dan termasuk golongan selection sort. Walaupun lebih lambat daripada quick sort pada kebanyakan mesin , tetapi heap sort mempunyai keunggulan yaitu kompleksitas algoritma pada kasus terburuk adalah n log n.

            Algoritma pengurutan heap sort ini mengurutkan isi suatu larik masukan dengan memandang larik masukan sebagai suatu Complete Binary Tree (CBT). Setelah itu Complete Binary Tree (CBT) ini dapat dikonversi menjadi suatu heap tree. Setelah itu Complete Binary Tree (CBT) diubah menjadi suatu priority queue.

            Algoritma pengurutan heap dimulai dari membangun sebuah heap dari kumpulan data yang ingin diurutkan, dan kemudian menghapus data yang mempunyai nilai tertinggi dan menempatkan dalam akhir dari larik yang telah terurut. Setelah memindahkan data dengan nilai terbesar, proses berikutnya adalah membangun ulang heap dan memindahkan nilai terbesar pada heap tersebut dan menempatkannya dalam tempat terakhir pada larik terurut yang belum diisi data lain. Proses ini berulang sampai tidak ada lagi data yang tersisa dalam heap dan larik yang terurut penuh. Dalam implementasinya kita membutuhkan dua larik – satu untuk menyimpan heap dan satu lagi untuk menyimpan data yang sudah terurut.
Tetapi untuk optimasi memori, kita dapat menggunakan hanya satu larik saja.
Yaitu dengan cara menukar isi akar dengan elemen terakhir dalam heap tree.
Jika memori tidak menjadi masalah maka dapat tetap menggunakan dua larik yaitu larik masukan dan larik hasil.

Algoritma Untuk Heap Sort

Berikut merupakan algoritma dari heap sort : 

1. Representasikan Heap dengan n elemen dalam sebuah array A[n]

2.      Elemen root tempatkan pada A[1]

3.      Elemen A[2i] adalah node kiri dibawah A[i]

4.      Elemen A[2i+1] adalah node kanan dibawah A[i]

5.      Contoh: array A=[16  14  10  8  7  9  3  2  4  1]  mewakili binary-heap sbb:

6.      Ambil nilai root (terbesar) A[1..n-1] dan pertukarkan dengan elemen terakhir dalam array, A[n]

7.      Bentuk Heap dari (n-1) elemen, dari A[1] hingga A[n-1]

8.      Ulangi langkah 6 dimana indeks terakhir berkurang setiap langkah.

Contoh Heap Sort

Terdapat data 16, 14, 10, 8, 7, 9, 2, 4, 1. Data-data tersebut dimasukkan dalam tree secara langsung dari atas ke bawah dan dari kiri ke kanan.

Selanjutnya dilakukan heap sort seperti pada gambar berikut :

Perbandingan Heap Sort Dengan Algoritma Pengurutan Lain

            Heapsort hampir setara dengan quick sort, algoritma pengurutan data lain berdasarkan perbandingan yang sangat efisien. Quick sort sedikit lebih cepat, karena cache dan faktor-faktor lain, tetapi pada kasus terburuk kompleksitasnya O(n), yang sangat lambat untuk data yang berukuran sangat besar. Lalu karena heap sort memiliki (N log N) maka sistem yang memerlukan pengamanan yang ketat biasa memakai heap sort sebagai algoritma pengurutannya. Heap sort juga sering dibandingkan dengan merge sort, yang mempunyaikompleksitas algoritma yang sama, tetapi kompleksitas ruang nya (n) yang lebih besar dari heap sort. Heap sort juga lebih cepat pada mesin dengan cache data yang kecil atau lambat