Heapsort

Definisi 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 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. Atau  dilakukan dengan cara membangun struktur data heap dan kemudian menerapkan langkah menghapus node heap. Pada awalnya, kondisi heap kosong. Kemudian, node heap di-insert satu per satu. Cara alternatif adalah, menampung data yang akan diurutkan dalam array, kemudian node pada bagian root di hapus. Jika heap adalah minimal heap, maka data pada root adalah data terkecil, terdapat 2 contoh heap yaitu MAXHEAP (nilai orangtua ≥ nilai anaknya) MIN HEAP (nilai orangtua ≤ nilai anaknya).

Algoritma Heap Sort
Pseudocode:
Judul: program_heap_sort
Deklarasi:	if (largest != i) {
Integer= A[100], i, length, le, ri, heapsize, largest	exchange A[i] <-> A[largest]
Deskripsi:	Heapify(A, largest)
Heapsort(A) {	}
BuildHeap(A)	}
for i <- length(A) downto 2 {
exchange A[1] <-> A[i]
heapsize <- heapsize -1
Heapify(A, 1)
}
BuildHeap(A) {
heapsize <- length(A)
for i <- floor( length/2 ) downto 1
Heapify(A, i)
}
Heapify(A, i) {
le <- left(i)
ri <- right(i)
if (le<=heapsize) and (A[le]>A[i])
largest <- le
else
largest <- i
if (ri<=heapsize) and (A[ri]>A[largest])
largest <- ri

Contoh Kasus Heap Sort

A[5]=1,5,2,4,3 = integer

Buatlah array A[5] dalam MAX HEAP Tree!

Solusi :

Pada gambar 1, angka 1 merupakan orangtua dan angka 4 merupakan anaknya. Pada heap tree max heap, nilai orangtua ≥ nilai anaknya. Karena pada gambar 1 nilai orangtua < nilai anaknya maka nilai orangtua dengan nilai anaknya di tukar. Sehingga heap tree pada gambar 1 berubah menjadi heap tree pada gambar 2.

Pada gambar 2, angka 4 merupakan orangtua dan angka 5 merupakan anaknya. Pada heap tree max heap, nilai orangtua ≥ nilai anaknya. Karena pada gambar 2 nilai orangtua < nilai anaknya maka nilai orangtua dengan nilai anaknya di tukar. Sehingga heap tree pada gambar 2 berubah menjadi heap tree pada gambar 3.

Pada gambar 3, angka 1 merupakan orangtua dan angka 3 merupakan anaknya. Pada heap tree max heap, nilai orangtua ≥ nilai anaknya. Karena pada gambar 3 nilai orangtua < nilai anaknya maka nilai orangtua dengan nilai anaknya di tukar. Sehingga heap tree pada gambar 3 berubah menjadi heap tree pada gambar 4.

Pada gambar 4, angka 3 merupakan orangtua dan angka 2 merupakan anaknya. Pada heap tree max heap, nilai orangtua ≥ nilai anaknya. Karena pada gambar 4 nilai orangtua ≥ nilai anaknya maka nilai orangtua dengan nilai anaknya tidak di tukar. Sehingga heap tree pada gambar 4 tidak berubah (gambar 5).