Heap sort
Heap sort adalah selection sort dengan cara yang lebih baik untuk menemukan nilai terbesar. Nilai yang belum terurut disimpan dalam heap, yaitu pohon yang disimpan di dalam daftar itu sendiri, tempat nilai terbesar selalu di puncak. Mengambilnya dan memperbaiki heap butuh sekitar log n langkah, bukan pemindaian penuh.
Pohon di dalam daftar
Binary heap adalah pohon yang tidak butuh pointer. Posisi 0 adalah akar, dan anak dari posisi i adalah posisi 2i + 1 dan 2i + 2, jadi posisi 1 dan 2 adalah anak akar, posisi 3 sampai 6 tingkat berikutnya, dan seterusnya. Setiap tingkat penuh kecuali yang terakhir, yang terisi dari kiri. Dalam max-heap setiap induk minimal sama besar dengan anak-anaknya, jadi nilai terbesar selalu di akar.
Menurunkan (sift down)
Satu operasi melakukan semua pekerjaan. Untuk menurunkan sebuah nilai, bandingkan dengan anak-anaknya. Jika anak yang lebih besar lebih besar dari nilai itu, keduanya ditukar, dan nilai itu dibandingkan dengan anak-anak barunya. Proses berhenti saat tidak ada anak yang lebih besar, atau saat mencapai dasar. Karena pohon hanya punya sekitar log₂ n tingkat, satu penurunan butuh paling banyak sekitar 2 log₂ n perbandingan.
Bangun heap, lalu urutkan
Untuk membangun heap, turunkan setiap induk, dari yang terakhir mundur sampai akar. Setiap subpohon sudah menjadi heap sebelum induknya diturunkan ke dalamnya. Lalu urutkan: tukar akar, yaitu nilai terbesar, dengan nilai terakhir heap. Nilai itu kini di tempat akhirnya. Heap berkurang satu, dan nilai yang sampai di akar diturunkan untuk memperbaikinya. Ulangi sampai tersisa satu nilai.
Contoh
Ambil 5, 1, 4, 2, 8. Membangun heap menurunkan 1 ke bawah 8, lalu 5 ke bawah 8, sehingga menjadi 8, 5, 4, 2, 1. Sekarang 8 ditukar ke akhir; 1 sampai di akar dan turun melewati 5 dan 2: 5, 2, 4, 1 | 8. Lalu 5 pindah ke akhir dan 1 turun melewati 4: 4, 2, 1 | 5, 8. Dua ronde lagi menyelesaikan daftar: 1, 2, 4, 5, 8, setelah 12 perbandingan dan 10 penukaran.
Kelebihan dan kekurangan
Waktu heap sort sebanding dengan n log n bahkan dalam kasus terburuk, dan ia tidak butuh memori tambahan. Quicksort bisa melambat hingga n² dan merge sort butuh buffer sepanjang daftar, jadi heap sort adalah cadangan yang aman: introsort, yang dipakai pustaka standar C++, beralih ke heap sort saat partisi quicksort memburuk. Di komputer nyata ia biasanya lebih lambat dari keduanya, karena melompat di antara posisi yang berjauhan dalam daftar, dan ia tidak stabil. J. W. J. Williams menerbitkan heap sort, bersama binary heap, pada 1964.
Jelajahi
Buka aplikasi dan tekan Langkah. Pohon di atas batang menampilkan heap: nilai yang sedang diturunkan punya warna sendiri, anak yang dibandingkan dengannya disorot, dan setiap penukaran tampil di pohon maupun di batang. Setelah heap terbentuk, lihat akar ditukar ke akhir, berubah hijau, dan keluar dari pohon.
Pertanyaan yang sering diajukan
Berapa kompleksitas waktu heap sort?
O(n log n) pada kasus terbaik, rata-rata, dan terburuk. Membangun heap butuh O(n), dan setiap dari n − 1 pengambilan butuh O(log n). Heap sort mengurutkan in-place dengan memori tambahan O(1).
Apa beda heap sort dan selection sort?
Keduanya mengambil nilai terbesar (atau terkecil) yang tersisa berulang kali. Selection sort menemukannya dengan memindai seluruh bagian yang belum terurut, n perbandingan setiap kali. Heap sort menyimpan bagian yang belum terurut dalam heap, tempat nilai terbesar sudah di puncak, dan memperbaiki heap hanya butuh sekitar log n perbandingan.
Selain mengurutkan, heap dipakai untuk apa?
Antrean prioritas (priority queue): heap langsung memberi item terbesar (atau terkecil) dan memungkinkan Anda menambah atau menghapus item dalam sekitar log n langkah. Penjadwal, algoritma jalur terpendek Dijkstra, dan simulasi peristiwa semuanya memakainya.
Apakah heap sort stabil?
Tidak. Menukar akar ke akhir memindahkan nilai sangat jauh, jadi nilai yang sama bisa berubah urutannya.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Coba heap sort