Ringkasan
Penyortiran Heap adalah penyortiran pemilihan pohon, yang merupakan peningkatan yang efektif pada penyortiran pemilihan langsung.
Tumpukan didefinisikan sebagai berikut: urutan elemen N (k1, k2, ..., kn), jika dan hanya jika puas:
Ini disebut tumpukan pada waktu itu. Seperti yang dapat dilihat dari definisi tumpukan, elemen atas heap (mis. Elemen pertama) harus menjadi item terkecil (tumpukan atas kecil) atau item terbesar (tumpukan atas besar).
Jika tumpukan disimpan dalam array satu dimensi, tumpukan sesuai dengan pohon biner yang sepenuhnya, dan nilai-nilai semua node non-daun (node dengan anak-anak) tidak lebih besar dari (atau tidak kurang dari) nilai-nilai anak-anak mereka, dan nilai-nilai dari simpul akar (elemen teratas dari heap) adalah yang terkecil (atau terbesar).
(a) Urutan tumpukan atas besar: (96, 83, 27, 38, 11, 09)
(B) Urutan tumpukan atas kecil: (12, 36, 24, 85, 47, 30, 53, 91)
Awalnya, urutan angka N yang akan diurutkan dianggap sebagai pohon biner yang disimpan secara berurutan (pohon biner penyimpanan array satu dimensi), menyesuaikan urutan penyimpanannya untuk membuatnya tumpukan, output elemen teratas dari tumpukan untuk mendapatkan elemen terkecil (atau terbesar) dari elemen N. Kemudian sesuaikan kembali elemen N-1 yang tersisa untuk menjadi tumpukan, output elemen teratas dari tumpukan, dan dapatkan elemen yang merupakan kecil kedua (atau besar kedua) di antara elemen N. Dan seterusnya sampai Anda akhirnya mendapatkan urutan yang dipesan dengan n node. Sebut proses heap proses ini.
Langkah & Contoh
Ada dua masalah yang harus dipecahkan dalam mengimplementasikan heap sorting:
(1) cara membangun N angka yang akan diurutkan menjadi tumpukan;
(2) Setelah mengeluarkan elemen atas tumpukan, cara menyesuaikan elemen N-1 yang tersisa untuk menjadikannya tumpukan baru.
Bangun metode heap (tumpukan atas kecil):
Proses membangun tumpukan untuk urutan awal adalah proses penyaringan berulang.
Pohon biner lengkap dari n node, kemudian simpul terakhir adalah subtree node n/2th.
Filter dimulai dengan subtree dengan node n/2 sebagai root (n/2 adalah simpul terakhir dengan subtree), sehingga subtree menjadi tumpukan.
Kemudian, filter subtrees dengan masing -masing node sebagai root secara berurutan ke depan untuk membuatnya menjadi tumpukan sampai simpul root.
Seperti yang ditunjukkan pada gambar, urutan yang tidak teratur dari proses awal membangun tumpukan: (49, 38, 65, 97, 76, 13, 27, 49)
(a) Urutan yang tidak dipesan, pohon biner awal, 97 (8/2 = 4 simpul) adalah simpul induk dari simpul terakhir (49).
(B) 97> = 49, ganti posisi, dan kemudian filter node sebelumnya 65 dari n/2.
(c) 13 <= 27 dan 65> = 13, ganti posisi 65 dan 13, dan kemudian ganti 38 (keduanya lebih besar dari itu, tidak diperlukan operasi), filter 49.
(D) 13 <= 38 dan 49> = 13, ganti posisi 49 dan 13, 49> = 27, ganti posisi 49 dan 27.
(e) Akhirnya mendapatkan tumpukan, 13 adalah angka minimum yang kami dapatkan.
Metode untuk menyesuaikan tumpukan (tumpukan atas kecil):
Tumpukan elemen M disediakan. Setelah mengeluarkan elemen teratas dari tumpukan, elemen M-1 tersisa. Elemen bawah tumpukan diumpankan ke bagian atas tumpukan, dan tumpukan dihancurkan, karena simpul akar tidak memenuhi sifat -sifat tumpukan.
Pertukaran simpul root dengan elemen yang lebih kecil di subtree kiri dan kanan.
Jika ditukar dengan subtree kiri: Jika tumpukan subtree kiri rusak, ulangi metode (2).
Jika ditukar dengan subtree kanan, ulangi metode (2) jika tumpukan subtree kanan dihancurkan.
Lanjutkan untuk melakukan operasi pertukaran di atas pada subtree yang tidak memenuhi properti tumpukan sampai node daun dan tumpukan dibangun.
Untuk menyesuaikan tumpukan, Anda hanya perlu mempertimbangkan node yang rusak, dan node lain tidak perlu disesuaikan.
Implementasi Kode (Java)
Jalankan kode dan bandingkan komentar dengan contoh langkah di atas untuk perbandingan.
Paket com.coder4j.main; heapsort kelas publik { / ** * Sesuaikan dengan tumpukan atas kecil (hasilnya dari besar ke kecil setelah penyortiran) * * @param array adalah array heap yang akan disesuaikan * @param s adalah posisi pubas yang disesuaikan * @param panjangnya adalah panjang array * / schray pubas {array pubas (array lengeng panjangnya adalah panjang array * / publy void {array heapy. tmp = array [s]; int child = 2 * s + 1; // posisi sistem simpul anak kiri.out.println ("simpul yang akan disesuaikan adalah: array [" + s + "] =" + tmp); while (anak <panjang) {// anak + 1 adalah anak yang tepat saat ini menyesuaikan simpul // jika ada anak yang tepat dan lebih kecil dari anak kiri, gunakan anak yang tepat untuk membandingkan dengan node, jika tidak gunakan anak kiri jika (anak + 1 <panjang && array [anak]> array [anak + 1]) {anak ++; } System.out.println ("akan dengan array anak [" + anak + "] =" + array [anak] + "bandingkan"); // Jika anak yang lebih kecil lebih kecil dari simpul ini jika (array [s]> array [anak]) {System.out.println ("Anak lebih kecil dari itu, swap position"); array [s] = array [anak]; // pindahkan anak yang lebih kecil ke atas dan ganti simpul saat ini untuk disesuaikan s = anak; // pindahkan simpul yang disesuaikan ke posisi asli dari array anak yang lebih muda [anak] = tmp; anak = 2 * S + 1; // Terus menilai apakah simpul yang akan disesuaikan perlu terus disesuaikan jika (anak> = panjang) {System.out.println ("Tidak ada anak, penyesuaian sudah berakhir"); } else {System.out.println ("Lanjutkan membandingkan dengan anak baru"); } // melanjutkan; } else {System.out.println ("Anak -anak lebih tua dari mereka, penyesuaian sudah berakhir"); break;// The current node to be adjusted is smaller than its left and right children, and it does not need to be adjusted, exit directly} } } /** * Adjust to a large top heap (the result is from small to large after sorting) * * @param array is the heap array to be adjusted* @param s is the position of the array element to be adjusted* @param length is the length of the array * */ public static void heapadjustb (int [] array, int s, int panjang) {int tmp = array [s]; int child = 2 * s + 1; // posisi sistem simpul anak kiri.out.println ("simpul yang akan disesuaikan adalah: array [" + s + "] =" + tmp); while (anak <panjang) {// anak + 1 adalah anak yang tepat saat ini menyesuaikan simpul // jika ada anak yang tepat dan lebih besar dari anak kiri, gunakan anak yang tepat untuk membandingkan dengan node, jika tidak gunakan anak kiri jika (anak + 1 <panjang && array [anak] <array [anak + 1]) {anak ++; } System.out.println ("akan dengan array anak [" + anak + "] =" + array [anak] + "bandingkan"); // Jika anak yang lebih tua lebih besar dari simpul ini jika (array [s] <array [anak]) {System.out.println ("Anak lebih besar dari itu, swap position"); array [s] = array [anak]; // pindahkan anak yang lebih tua ke atas dan ganti simpul saat ini untuk disesuaikan s = anak; // pindahkan simpul yang disesuaikan ke posisi asli dari array anak yang lebih tua [anak] = tmp; anak = 2 * S + 1; // Terus menilai apakah simpul yang akan disesuaikan perlu disesuaikan jika (anak> = panjang) {System.out.println ("Tidak ada anak, penyesuaian sudah berakhir"); } else {System.out.println ("Lanjutkan membandingkan dengan anak baru"); } // melanjutkan; } else {System.out.println ("Anak -anak lebih kecil dari mereka, penyesuaian sudah berakhir"); break;// The current node to be adjusted is larger than its left and right children, and exit directly without adjustment} } } /** * Heap sorting algorithm * * @param array * @param inverse true In reverse order, false in positive order*/ public static void heapSort(int[] array, boolean inverse) { // Initial heap// The position of the last node with a child i = (length - 1) / 2, untuk menyesuaikan setiap node ke atas agar sesuai dengan sistem heap.out.println ("Awal Heap Start"); untuk (int i = (array.length-1) / 2; i> = 0; i--) {if (inverse) {heapadjusts (array, i, array.length); } else {heapadjustb (array, i, array.length); }} System.out.println ("Awal Heap End"); untuk (int i = array.length-1; i> 0; i--) {// Sukihkan elemen atas heap h [0] dan elemen terakhir dalam heap int tmp = array [i]; array [i] = array [0]; Array [0] = TMP; // Setelah setiap pertukaran elemen atas tumpukan dan elemen terakhir dalam tumpukan, tumpukan harus disesuaikan jika (terbalik) {heapadjusts (array, 0, i); } else {heapadjustb (array, 0, i); }}} public static void main (string [] args) {int [] array = {49, 38, 65, 97, 76, 13, 27, 49}; heapsort (array, false); untuk (int i: array) {System.out.print (i + ""); }}}Hasil Menjalankan:
Node yang akan disesuaikan pada awal tumpukan awal adalah: array [3] = 97 Anak akan lebih kecil dengan array anak [7] = 49 Anak lebih kecil dengan anak, dan simpul yang akan disesuaikan pada akhir penyesuaian adalah: array [2] = 65 Anak lebih kecil dengan array anak [5] = 13 anak lebih kecil, dan anak -anaknya node lebih kecil dengan node anak -anak [5] = 13 anak lebih kecil, dan anak -anaknya node pada node lebih kecil dengan NODE NODE NODA [5] = 13 Anak lebih kecil, dan anak -anak itu node lebih kecil dengan node anak -anak [5] = 13 Anak lebih kecil, dan anak -anaknya node pada node lebih kecil dengan node anak [5] = 13 anak lebih kecil, dan anak -anaknya node pada node pada node pada noda [5] = 13 anak lebih kecil, dan anaknya node pada node lebih kecil dengan node anak -anak [5] = 13 anak lebih kecil, dan anaknya node lebih kecil dengan node anak -anak [5]; = 38 Anak lebih besar dengan array anak [3] = 49 Anak lebih besar dengan susunan anak [0] = 49 Anak lebih kecil dengan susunan anak [2] = 13 Anak lebih kecil dengan susunan anak [6] = 27 anak lebih kecil dari posisi pertukaran, dan tidak ada anak dalam posisi pertukaran. Node yang akan disesuaikan setelah penyesuaian adalah: array [0] = 97 Anak lebih kecil dari anak. Anak lebih kecil dari anak. Posisi pertukaran terus dibandingkan dengan anak baru. Anak adalah array [6] = 49 Anak lebih kecil dari posisi pertukaran, dan tidak ada anak di posisi pertukaran. Node yang akan disesuaikan setelah penyesuaian adalah: array [0] = 97 Anak lebih kecil dari anak. Anak lebih kecil dari anak. Anak lebih kecil dari anak. Anak adalah array [1] = 38 Anak lebih kecil dari anak. Anak adalah array [3] = 49 Anak lebih kecil dari anak. Anak lebih kecil dari posisi pertukaran. Node yang akan disesuaikan setelah penyesuaian adalah: array [0] = 65 Anak adalah array [1] = 49 Anak lebih kecil dari anak, dan posisi pertukaran terus dibandingkan dengan anak baru. Anak akan lebih besar dari anak. Node yang akan disesuaikan setelah penyesuaian adalah: array [0] = 76 Anak lebih besar dari anak. Node yang akan disesuaikan setelah penyesuaian adalah: array [0] = 76 Anak lebih kecil dari anak. Node yang akan disesuaikan setelah penyesuaian adalah: array [0] = 49 Anak lebih kecil dari anak. Node yang akan disesuaikan setelah penyesuaian adalah: array [0] = 97 Anak lebih kecil dari anak. Node yang akan disesuaikan setelah penyesuaian adalah: array [0] = 97 76 65 49 49 38 27 13
PS: Perbedaan antara penyortiran heap dan penyortiran insert langsung
Dalam urutan seleksi langsung, untuk memilih catatan dengan kata kunci terkecil dari R [1..n], perbandingan N-1 harus dilakukan, dan kemudian pilih catatan dengan kata kunci terkecil di R [2..n], perbandingan N-2 harus dilakukan. Faktanya, dalam perbandingan N-2 berikut, banyak perbandingan mungkin telah dibuat dalam perbandingan N-1 sebelumnya, tetapi karena hasil perbandingan ini tidak dipertahankan dalam urutan sebelumnya, operasi perbandingan ini diulangi selama urutan berikutnya.
Penyortiran tumpukan dapat menghemat sebagian hasil perbandingan melalui struktur pohon, yang dapat mengurangi jumlah perbandingan.