SIMULASI PENGURUTAN DATA DENGAN ALGORITMA HEAP SORT

Abstract

Struktur data dari algoritma Heap Sort adalah sebuah pohon biner sempurna yang memenuhi properti heap. Node akar (root node) memiliki data terbesar atau terkecil yang terdapat pada pohon. Demikian juga pada subtree-nya, dimana node induk (parent) memiliki data yang paling besar atau paling kecil dibandingkan dengan data pada kedua anaknya (child node sebelah kiri atau sebelah kanan). Struktur data heap adalah sebuah objek array yang dapat divisualisasikan dengan sebuah complete binary tree. Hubungan antara elemen dari array dan node pada pohon merupakan hubungan korespondensi satu satu. Pohon diisi secara penuh pada semua level, kecuali kemungkinan terkecil, dimana diisi dari kiri sampai ke sebuah titik. Semua node dari heap juga memenuhi relasi bahwa nilai kunci pada setiap node minimal sama besar dengan nilai dari node anaknya. Setelah menyelesaikan perangkat lunak bantu pemahaman Heap Sort, perangkat lunak menjelaskan algoritma pengurutan Heap Sort dan gambar keadaan pohon biner secara bertahap serta menampilkan Form Teori, sehingga dapat membantu pemahaman mengenai pengurutan dengan metode Heap Sort. Algoritma pengurutan Heap Sort merupakan salah satu metode pengurutan tercepat setelah Merge Sort dan Quick Sort dengan kompleksitas O(n log n). Kompleksitas prosedur Build-Heap adalah O(n), kompleksitas prosedur Heapify adalah O(log n), sehingga kompleksitas algoritma Heap Sort adalah O(n log n).

Kata Kunci    : Heap Sort, Merge Sort, Quick Sort, kompleksitas O(n log n).