1. Pengetahuan Dasar
Apa yang biasanya kami sebut tumpukan mengacu pada tumpukan biner, yang juga disebut pohon biner lengkap atau pohon biner yang kira -kira lengkap. Tumpukan biner dibagi menjadi tumpukan terbesar dan tumpukan terkecil.
Penyortiran Heap mengacu pada algoritma penyortiran yang dirancang menggunakan struktur data heap, yang merupakan semacam pemilihan penyortiran. Anda dapat dengan cepat menemukan elemen dari indeks yang ditentukan menggunakan karakteristik array. Array dapat secara langsung mendapatkan elemen berdasarkan indeks, dan kompleksitas waktu adalah O (1), yaitu konstanta, sehingga mereka sangat efisien untuk perolehan nilai.
Karakteristik tumpukan maksimum adalah sebagai berikut:
Karakteristik tumpukan minimum adalah sebagai berikut:
2. Pikiran algoritma
1. Gagasan algoritma dari tumpukan terbesar adalah:
Pertama, R awal [0 ... N-1] dibangun ke tumpukan terbesar. Pada saat ini, ini adalah tumpukan yang tidak tertib. Tumpukan atas adalah elemen terbesar dan kemudian rekor terakhir R [n-1] dari area yang tidak tertib ditukar. Ini menghasilkan area baru R [0 ... n-2] dan area yang dipesan R [n-1], dan memenuhi R [0 ... n-2] .keys ≤ r [n-1] .key
Karena R pertama [0 ... N-2] mungkin tidak memenuhi sifat-sifat tumpukan maksimum setelah pertukaran, R pertama [0 ... n-2] disesuaikan dengan tumpukan maksimum sampai hanya elemen terakhir r [0] disesuaikan.
Setelah jenis tumpukan maksimum selesai, itu sebenarnya urutan naik. Setiap kali tumpukan disesuaikan, elemen terbesar diperoleh dan kemudian ditukar dengan elemen terakhir dari tumpukan saat ini. Oleh karena itu, urutan akhir yang diperoleh adalah urutan naik.
2. Gagasan algoritma dari tumpukan terkecil adalah:
Pertama, R awal [0 ... N-1] dibangun ke tumpukan terkecil. Pada saat ini, ini adalah tumpukan yang tidak tertib. The top element of the heap is the smallest element and then exchanges the top R[0] with the last R[n-1] of the unordered area, thereby obtaining the new unordered heap R[0…n-2] and the ordered heap R[n-1], and satisfying R[0…n-2].keys >= R[n-1].key
Karena R pertama [0 ... N-2] mungkin tidak memenuhi sifat-sifat tumpukan minimum setelah pertukaran, R pertama [0 ... N-2] disesuaikan dengan tumpukan minimum sampai hanya elemen terakhir dari R [0] yang disesuaikan dan tumpukan minimum diurutkan. Setelah pemesanan tumpukan minimum selesai, itu sebenarnya adalah urutan yang menurun. Setiap kali tumpukan disesuaikan, elemen terkecil diperoleh dan kemudian ditukar dengan elemen terakhir dari tumpukan saat ini yang tidak tertib, sehingga urutan yang diperoleh dalam urutan menurun.
Kiat: Proses penyortiran tumpukan sebenarnya adalah proses memperluas area yang dipesan secara terus menerus, dan kemudian secara terus -menerus mengurangi area yang tidak teratur sampai hanya ada area yang dipesan.
3. Analisis proses penyortiran
Karena algoritma relatif abstrak, di sini kami secara langsung menggambarkan proses penyortiran heap dengan memberikan contoh kecil. Selanjutnya, kami menggunakan urutan yang tidak tertib ini untuk menggunakan tumpukan terbesar untuk penyortiran tumpukan, dan urutan yang dihasilkan adalah urutan naik (ASC).
Urutan tidak tertib: 89, -7,999, -89,7,0, -888,7, -7
Langkah 1: Inisialisasi tumpukan maksimum untuk membangun:
Langkah 2: Pertukaran elemen maksimum 999 di bagian atas tumpukan dengan elemen terakhir dari area yang tidak tertib, sehingga 999 menjadi area yang dipesan. Setelah pertukaran, -7 menjadi tumpukan atasan. Karena -7 bukan elemen terbesar di area yang tidak tertib, perlu untuk menyesuaikan area yang tidak tertib sehingga nilai maksimum 89 di area yang tidak tertib menjadi tumpukan atas, sehingga -7 dan 89 dipertukarkan. Setelah pertukaran, subtree kanan 89 tidak memenuhi sifat tumpukan terbesar, sehingga subtree kanan harus disesuaikan dengan tumpukan terbesar, sehingga -7 harus ditukar dengan 0, seperti yang ditunjukkan pada gambar di bawah ini:
Dari gambar, ketika -7% 89% swap, bagian atas tumpukan adalah elemen terbesar, tetapi anak kiri -7 adalah 0 dan anak yang tepat adalah -888. Sejak -7 <0, simpul -7 tidak memenuhi sifat tumpukan, sehingga perlu disesuaikan. Jadi, 0 dipertukarkan dengan -7.
Kemudian ulangi langkah kedua sampai menjadi area yang dipesan.
Akhirnya: Apa yang diperoleh adalah urutan naik
4. Kompleksitas waktu
Waktu penyortiran tumpukan terutama terdiri dari overhead waktu untuk membangun tumpukan awal dan berulang kali menyesuaikan tumpukan. Karena penyortiran tumpukan tidak stabil, kompleksitas waktu yang didapatnya akan lebih besar sesuai dengan situasi aktual, sehingga hanya dapat mengambil kompleksitas waktu rata -rata.
Kompleksitas waktu rata -rata adalah: o (n * log2 (n))
Operasi penyortiran heap yang memakan waktu meliputi: heap awal + penyesuaian berulang heap, dan kompleksitas waktu adalah sebagai berikut:
1. Gedung Tumpukan Awal: Setiap node induk akan membandingkan dan bertukar dengan node anak kiri dan kanan hingga 2 kali, sehingga kompleksitas terkait dengan jumlah node induk. Berdasarkan 2x <= n (x adalah jumlah kali N elemen dapat dilipat menjadi dua, yaitu, jumlah node induk), diperoleh x = log2n. Yaitu, o (log2n)
2. Penyesuaian berulang dari heap: Karena hasil perbandingan array dicatat selama inisialisasi tumpukan, jenis heap tidak sensitif terhadap urutan array dari urutan asli, dan situasi terbaik mirip dengan kasus terburuk. Elemen Top Top perlu diekstraksi N-1 kali. Setiap kali elemen heap atas diambil, tumpukan perlu dibangun kembali (O (Rekonstruksi Tumpukan) <O (Heap Awal)). Jadi kurang dari O (n-1) * O (log2n)
Penggunaan yang Disarankan:
Karena berapa kali inisialisasi heap perlu dibandingkan, Heap Sorting lebih cocok untuk situasi di mana jumlah data sangat besar (juta data atau lebih). Karena penyortiran cepat yang efisien didasarkan pada implementasi rekursif, kesalahan overflow stack terjadi ketika volume data sangat besar.
5. Kode Sampel Java
heapsort kelas publik {private static int [] sort = new int [] {1,0,10,20,3,5,6,4,9,8,12, 17,34,11}; public static void main (string [] args) {buildMaxHeapify (sort); heapsort (sort); cetak (sort); } private static void buildMaxHeAPIFy (int [] data) {// Hanya mereka yang tidak perlu anak-anak yang perlu membuat tumpukan maksimum, mulai dari simpul induk terakhir int startIndex = getParentIndex (data.length-1); // Buat heap maksimum dari ujung, dan ini adalah heap yang benar untuk (int i = startindex; i> = 0; }}/***Buat tumpukan maksimum**@paramdata*@paramheapsize membutuhkan ukuran tumpukan maksimum, yang umumnya digunakan dalam pengurutan, karena nilai maksimum ditempatkan pada akhirnya, ujungnya tidak lagi diklasifikasikan sebagai heap maksimum*@paramindex Posisi di mana heap maksimum saat ini diperlukan*/private static void {private heap*@paramIndex. dengan node anak kiri dan kanan int kiri = getchildleftIndex (indeks); int right = getChildrightIndex (index); int terbesar = indeks; if (kiri <heapsize && data [index] <data [kiri]) {terbesar = kiri; } if (kanan <heapsize && data [terbesar] <data [kanan]) {terbesar = kanan; } // Setelah mendapatkan nilai maksimum, mungkin perlu ditukar. Jika ditukar, anak -anaknya mungkin bukan tumpukan terbesar. Perlu disesuaikan jika (terbesar! = Indeks) {int temp = data [indeks]; data [indeks] = data [terbesar]; data [terbesar] = temp; MaxHeAPIFY (data, heapsize, terbesar); }} /***Penyortiran, nilai maksimum ditempatkan di akhir. Meskipun data adalah tumpukan terbesar, itu menjadi tambahan setelah penyortiran * *@paramdata */private static void heapsort (int [] data) {// pertukaran dengan header di akhir, sesuaikan tumpukan maksimum setelah pertukaran (int i = data.length-1; i> 0; i-) {int temp = data [0]; data [0] = data [i]; data [i] = temp; maxheapify (data, i, 0); }} / ** *paramCurrent *@return * / private static int getParentIndex (int saat ini) {return (current-1) >> 1; } / ** *Posisi simpul anak sekarang Perhatikan tanda kurung, dan prioritas penambahan lebih tinggi * *@paramcurrent *@@return * / private int getchildleftIndex (int saat ini) {return (saat ini << 1) +1; } / ** *Posisi simpul anak yang tepat * *@paramcurrent *@return * / private static int getChildRightIndex (int saat ini) {return (saat ini << 1) +2; } private static void print (int [] data) {int pre = -2; untuk (int i = 0; i <data.length; i ++) {if (pre <(int) getLog (i+1)) {pre = (int) getLog (i+1); System.out.println (); } System.out.print (data [i]+"|"); }}/** *Logo dengan basis 2 * *@paraparam *@return */private static double getLog (param ganda) {return math.log (param) /math.log (2); }}