Tumpukan adalah struktur penting dalam struktur data. Setelah memahami konsep dan pengoperasian "Heap", Anda dapat dengan cepat menguasai penyortiran tumpukan.
Konsep heap
Heap adalah pohon biner lengkap khusus. Jika nilai semua node dari pohon biner yang benar -benar tidak lebih kecil dari anak -anak mereka, itu disebut tumpukan akar yang besar (atau tumpukan atas besar); Jika nilai semua node tidak lebih besar dari anak -anak mereka, itu disebut tumpukan akar kecil (atau tumpukan atas kecil).
Dalam array (menyimpan simpul root di nomor subskrip 0), mudah untuk mendapatkan persamaan berikut (kedua persamaan ini sangat penting):
1. Node dengan subskrip adalah I, dan koordinat simpul induk adalah (I-1)/2;
2. Node dengan subskrip adalah I, koordinat simpul anak kiri adalah 2*i+1, dan simpul anak yang tepat adalah 2*i+2.
Tumpukan Pembentukan dan Pemeliharaan
Tumpukan dapat mendukung banyak operasi, tetapi sekarang kami hanya peduli tentang dua masalah:
1. Diberikan array yang tidak berurutan, bagaimana membangunnya sebagai tumpukan?
2. Setelah menghapus elemen atas tumpukan, bagaimana cara menyesuaikan komposisi dengan tumpukan baru?
Mari kita lihat pertanyaan kedua terlebih dahulu. Misalkan kita sudah memiliki tumpukan akar besar yang sudah siap pakai. Sekarang kami menghapus elemen root, tetapi kami tidak memindahkan elemen lainnya. Pikirkan tentang apa yang terjadi: elemen root kosong, tetapi elemen -elemen lain masih mempertahankan sifat -sifat tumpukan. Kita dapat memindahkan elemen terakhir (nama kode a) ke posisi elemen root. Jika ini bukan kasus khusus, sifat -sifat tumpukan dihancurkan. Tetapi ini hanya karena A lebih kecil dari salah satu elemen anaknya. Jadi, kita dapat mengganti dan elemen anak ini ke posisi. Jika A lebih besar dari semua elemen anaknya, tumpukan disesuaikan; Jika tidak, ulangi proses di atas, elemen A terus "tenggelam" dalam struktur pohon sampai sesuai, dan array mengembalikan sifat -sifat tumpukan. Proses di atas umumnya disebut "penyaringan", dan arahnya jelas dari atas ke bawah.
Ini benar ketika menghapus elemen, dan begitu juga memasukkan elemen baru. Perbedaannya adalah bahwa kami meletakkan elemen baru di ujungnya dan kemudian membandingkannya dengan node induknya, yaitu menyaringnya dari bawah ke atas.
Jadi, bagaimana menyelesaikan masalah pertama?
Banyak buku tentang struktur data yang saya baca disaring dari simpul non-daun pertama sampai elemen root disaring. Metode ini disebut "Metode Penyaringan", yang memerlukan penyaringan loop elemen N/2.
Tapi kita juga bisa belajar dari gagasan "menciptakan sesuatu dari ketiadaan". Kita dapat menganggap elemen pertama sebagai tumpukan dan kemudian terus -menerus menambahkan elemen baru ke dalamnya. Metode ini disebut "Metode Sisipkan", yang membutuhkan penyisipan loop elemen (N-1).
Karena metode penyaringan dan metode penyisipan berbeda, tumpukan yang mereka buat umumnya berbeda untuk data yang sama.
Setelah pemahaman yang kasar tentang tumpukan, penyortiran tumpukan adalah hal yang wajar.
Tinjauan/Ide Algoritma
Kita membutuhkan urutan naik, apa yang harus kita lakukan? Kita dapat membangun tumpukan minimum dan kemudian mengeluarkan elemen root setiap kali. Namun, metode ini membutuhkan ruang ekstra (jika tidak, ia akan menyebabkan banyak gerakan elemen, dan kompleksitasnya akan melambung ke O (n^2)). Bagaimana jika kita membutuhkan penyortiran di tempat (mis., Tidak ada kompleksitas ruang O (n) yang diizinkan)?
Ada jalan. Kita dapat membangun tumpukan maksimum, dan kemudian kita mengeluarkan nilai maksimum di posisi terakhir, dan nilai maksimum kedua di posisi terakhir ... karena output elemen maksimum setiap kali akan membebaskan ruang pertama, kita hanya dapat menempatkan elemen seperti itu tanpa membutuhkan ruang ekstra. Ide yang sangat indah, kan?
heapsort kelas publik {public static void main (string [] args) {int [] arr = {50, 10, 90, 30, 70, 40, 80, 60, 20}; System.out.println ("Sebelum menyortir:"); untuk (int i = 0; i <arr.length; i ++) {System.out.print (arr [i]+""); } // heap penyortiran heapsort (arr); System.out.println (); System.out.println ("Setelah setelah penyortiran:"); untuk (int i = 0; i <arr.length; i ++) {System.out.print (arr [i]+""); }} / *** Heap sort* / private static void heapsort (int [] arr) {// buat urutan yang akan diurutkan menjadi tumpukan atas besar untuk (int i = arr.length / 2; i> = 0; i-) {heapadjust (arr, i, arr.length); } // Secara bertahap menukar simpul root dari setiap nilai maksimum dengan elemen akhir, dan menyesuaikan pohon biner untuk menjadikannya tumpukan atas yang besar untuk (int i = arr.length-1; i> 0; i--) {swap (arr, 0, i); // pertukaran rekor teratas heap dengan catatan terakhir dari heapadjust selanjutnya yang saat ini tidak disortir (arr, 0, i); // Setelah pertukaran, perlu untuk memeriksa kembali apakah tumpukan memenuhi tumpukan besar. If it does not meet, it needs to be adjusted} } /** * Process of building the heap* @param arr Array that needs to be sorted* @param i The number of the root node of the heap that needs to be built* @param n The length of the array*/ private static void heapAdjust(int[] arr, int i, int n) { int child; ayah int; untuk (ayah = arr [i]; leftchild (i) <n; i = anak) {anak = leftchild (i); // Jika subtree kiri lebih kecil dari subtree kanan, Anda perlu membandingkan subtree kanan dengan node induk jika (anak! = N - 1 && arr [anak] <arr [anak+1]) {anak ++; // Tingkatkan nomor seri dengan 1, menunjuk ke subtree kanan} // Jika simpul induk lebih kecil dari simpul anak, Anda perlu bertukar jika (ayah <arr [anak]) {arr [i] = arr [anak]; } else {break; // Struktur tumpukan atas yang besar tidak dihancurkan, tidak diperlukan penyesuaian}} arr [i] = ayah; } // Dapatkan Node Anak Kiri Private Static Int LeftChild (int i) {return 2 * i + 1; } // Posisi elemen swap Private static void swap (int [] arr, int index1, int index2) {int tmp = arr [index1]; arr [index1] = arr [index2]; arr [index2] = tmp; }}