- Diturunkan
- Dibandingkan
- Ditukar
- Di tempatnya
Heap sort
Heap sort membaca daftar sebagai pohon biner dan menyusunnya ulang menjadi max-heap, tempat setiap induk minimal sama besar dengan anak-anaknya. Nilai terbesar lalu berada di puncak. Tukar nilai itu ke akhir, tempat ia menetap, perbaiki heap, lalu ulangi. Aplikasi ini menggambar heap sebagai pohon di atas batang, sehingga Anda bisa mengikuti setiap nilai saat diturunkan. Tekan Putar untuk melihat pengurutan, atau Langkah dan Mundur untuk maju satu perbandingan setiap kali. Geser penggeser langkah untuk melompat ke mana saja. Pohon di atas batang menampilkan nilai yang sama sebagai heap. Kotak-kotak menghitung perbandingan, penukaran, dan nilai yang diambil dari heap. Pilih jumlah batang, urutan awalnya, atau ketik angka sendiri. Saat papan dipilih, tombol panah melangkah, spasi memutar dan menjeda, serta Home dan End melompat ke awal dan akhir.
Cara kerjanya
- Pilih jumlah batang dan urutan awalnya: acak, hampir terurut, terbalik, atau dengan sedikit nilai unik. Atau ketik angka sendiri.
- Tekan Putar, atau gunakan Langkah dan Mundur untuk maju satu perbandingan setiap kali. Geser penggeser langkah untuk melompat ke mana saja dalam pengurutan.
- Amati pohonnya: pertama setiap induk diturunkan sampai heap terbentuk, lalu akar ditukar ke akhir dan heap menyusut satu.
Cara kerja heap sort
Baca daftar sebagai pohon: nilai di posisi i punya anak di posisi 2i + 1 dan 2i + 2. Bangun max-heap dengan menurunkan setiap induk, mulai dari induk terakhir: selama sebuah nilai lebih kecil dari anaknya yang lebih besar, keduanya ditukar. Saat akar memegang nilai terbesar, tukar dengan nilai terakhir heap. Nilai itu kini sudah tetap, heap berkurang satu, dan akar baru diturunkan agar kembali menjadi heap. Ulangi sampai heap kosong.
Selalu n log n, in-place
Pohon punya sekitar log₂ n tingkat, jadi setiap penurunan butuh paling banyak sekitar 2 log₂ n perbandingan, dan membangun heap butuh kurang dari 2n. Karena itu kasus terburuk heap sort sekitar 2n log₂ n perbandingan, tanpa buffer: untuk 40 nilai, paling banyak 352. Tidak seperti quicksort, ia tidak punya masukan yang buruk, dan tidak seperti merge sort, ia tidak butuh memori tambahan. Dalam praktiknya ia biasanya lebih lambat dari keduanya, karena melompat-lompat di dalam daftar, dan ia tidak stabil.
Pertanyaan yang sering diajukan
Bagaimana cara kerja heap sort?
Heap sort mengubah daftar menjadi max-heap, yaitu pohon yang disimpan di dalam daftar, tempat setiap induk minimal sama besar dengan anak-anaknya. Lalu ia berulang kali menukar nilai terbesar, di akar, ke akhir heap dan menurunkan akar baru untuk memperbaiki heap.
Apa itu heap?
Pohon biner lengkap yang disimpan di dalam daftar tanpa pointer: anak dari posisi i adalah posisi 2i + 1 dan 2i + 2. Dalam max-heap setiap induk minimal sama besar dengan anak-anaknya, jadi nilai terbesar selalu di akar, posisi 0.
Mengapa membangun heap itu cepat?
Sebagian besar nilai berada di dekat dasar pohon dan hanya bisa turun satu atau dua tingkat. Jika kerja di semua tingkat dijumlahkan, seluruh pembangunan heap butuh kurang dari 2n perbandingan, bukan n log n.
Apakah heap sort stabil?
Tidak. Menukar akar ke akhir memindahkan nilai sangat jauh, jadi nilai yang sama bisa berubah urutan.
Apakah angka saya dikirim ke mana pun?
Tidak. Pengurutan berjalan di browser Anda, dan pengaturan terakhir Anda tersimpan di penyimpanan lokal browser ini.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Ke Editor