Heapsort merupakan algoritma pengurutan in-place yang digunakan dalam ilmu komputer untuk menghasilkan algoritma pengurutan yang lebih efisien dibandingkan algoritma pengurutan lainnya seperti Selection Sort, Insertion Sort, dan Bubble Sort. Algoritma ini dikembangkan oleh JWJ Williams pada tahun 1964, dan masih banyak digunakan hingga saat ini.
Heapsort bekerja dengan terlebih dahulu menyusun data masukan menjadi Binary Max Heap. Binary Max Heap adalah struktur data yang memenuhi properti heap, dimana node induk selalu bernilai lebih besar atau sama dibandingkan node turunannya. Setelah struktur data ini dibuat, node akar (yang memiliki nilai maksimum di heap) ditukar dengan elemen terakhir dalam urutan data dan ukuran heap dikurangi sebesar 1. Proses ini diulangi hingga heap selesai. diurutkan.
Kompleksitas Heapsort bergantung pada tipe struktur data yang digunakan untuk merepresentasikan data. Jika struktur datanya merupakan struktur data linier, maka kompleksitas waktu terburuk Heapsort adalah O(nlogn). Dalam kasus pohon pencarian biner yang menyeimbangkan diri, kompleksitas waktu terburuk dari Heapsort adalah O(n).
Heapsort adalah algoritma yang efisien dan cocok untuk menyortir data dalam jumlah besar. Karena kompleksitas ruangnya yang rendah, ini juga sering digunakan dalam situasi dengan memori terbatas. Karena alasan ini, Heapsort adalah algoritma yang populer di banyak bidang ilmu komputer.
