Pengurutan heap
Menyusun daftar menjadi heap, yaitu pohon tempat setiap induk lebih besar dari anak-anaknya. Lalu nilai terbesar dipindah ke ujung, berulang kali.
- Ω(n log n)
- Θ(n log n)
- O(n log n)
- O(1)
- tidak
- ya
Kasus terbaik: bagaimana waktu tumbuh seiring ukuran daftar n saat input paling mudah bagi algoritma ini.
Rata-rata: pertumbuhan waktu biasa terhadap n. Pada n², jumlah nilai 2 kali lipat butuh sekitar 4 kali waktu; n log n jauh lebih lambat.
Kasus terburuk: pertumbuhan pada input tersulit. Berguna saat kecepatan tidak boleh turun.
Memori: berapa memori tambahan yang dibutuhkan selain daftar. 1 berarti beberapa variabel, n berarti salinan daftar.
Stabil: dua nilai yang sama tetap dalam urutan aslinya. Penting saat mengurutkan data menurut satu kolom.
Tanpa memori tambahan: mengurutkan di dalam daftar itu sendiri, tanpa daftar kedua.
- dibandingkan
- dipindahkan
- di posisi akhir
Coba ini: Pilih daftar terbalik. Heap terbentuk hampir tanpa pertukaran, lalu tiap putaran memindahkan nilai terbesar ke ujung.
Cara kerjanya
Heap disimpan di dalam daftar itu sendiri: anak dari nilai di posisi i ada di posisi 2i+1 dan 2i+2, dan nilai terbesar selalu di depan. Tukar nilai itu ke ujung, kecilkan heap satu posisi, lalu perbaiki. Bagian terurut tumbuh dari kanan.
Kapan ini pilihan yang tepat
Saat Anda butuh kecepatan yang tetap baik bahkan di kasus terburuk tanpa memori tambahan, misalnya di perangkat kecil. Rata-rata ia lebih lambat dari pengurutan cepat, jadi sering dipakai sebagai cadangan.