1. Saya harus berbicara tentang pohon biner
Untuk memahami tumpukannya, Anda harus terlebih dahulu memahami pohon biner. Dalam ilmu komputer, pohon biner adalah struktur pohon dengan paling banyak dua subtree per node. Biasanya subtree disebut "Subtree Kiri" dan "Subtree Kanan". Pohon biner sering digunakan untuk menerapkan pohon pencari biner dan tumpukan biner.
Setiap simpul pohon biner memiliki paling banyak dua subtree (node dengan derajat lebih besar dari 2). Subtre dari pohon biner dapat dibagi menjadi kiri dan kanan, dan tatanan tidak dapat dibalik. Lapisan i -th dari pohon biner memiliki paling banyak 2i - 1 node; pohon biner dengan kedalaman k memiliki paling banyak 2k - 1 simpul; Untuk setiap pohon biner, jika jumlah node terminal adalah N0 dan jumlah node dengan derajat 2 adalah n2, n0 = n2 + 1.
Ada tiga perbedaan utama antara pohon dan pohon biner:
Jumlah node di pohon setidaknya 1, sedangkan jumlah node di pohon biner bisa 0.
Tidak ada batasan pada tingkat maksimum node di pohon, sedangkan tingkat maksimum node di pohon biner adalah 2
Tidak ada perbedaan antara kiri dan kanan di node pohon, sementara tidak ada perbedaan antara kiri dan kanan di node pohon biner.
Pohon biner dibagi menjadi pohon -pohon biner lengkap dan pohon biner penuh.
Pohon biner penuh: pohon dengan kedalaman k dan memiliki 2k - 1 simpul disebut pohon biner penuh
(Pohon biner penuh dengan kedalaman 3)
Pohon biner lengkap: Pohon biner dengan n node dengan kedalaman k. Ini disebut pohon biner lengkap jika dan hanya jika masing -masing node sesuai dengan node dengan nomor urutan 1 hingga N dalam pohon biner penuh dengan kedalaman k.
(Pohon biner penuh dengan kedalaman 3)
2. Apa itu tumpukan?
Tumpukan (tumpukan biner) dapat dianggap sebagai pohon biner lengkap. Properti "luar biasa" dari pohon biner lengkap adalah bahwa, kecuali untuk lapisan bawah, setiap lapisan penuh, yang memungkinkan tumpukan diwakili oleh array (pohon biner umum biasanya diwakili oleh daftar yang ditautkan sebagai wadah dasar), dan setiap node sesuai dengan elemen dalam array.
Gambar berikut menunjukkan hubungan antara tumpukan dan array
(Hubungan antara tumpukan dan array)
Untuk subskrip I yang diberikan dari sebuah node, dapat dengan mudah dihitung untuk subskrip dari simpul induk dan simpul anak dari node ini:
Induk (i) = lantai (i/2), subskrip node induk dari i
Kiri (i) = 2i, subskrip simpul anak kiri i
Kanan (i) = 2i + 1, subskrip simpul anak yang tepat dari i
Umumnya ada dua jenis tumpukan biner: tumpukan terbesar dan tumpukan terkecil.
Tumpukan maksimum:
Nilai elemen maksimum dalam tumpukan maksimum muncul di simpul root (atas tumpukan)
Nilai elemen dari setiap simpul induk dalam tumpukan lebih besar dari atau sama dengan simpul anaknya (jika ada)
(Tumpukan maksimum)
Tumpukan Minimum:
Nilai elemen minimum di tumpukan minimum muncul di simpul root (atas tumpukan)
Nilai elemen dari setiap simpul induk dalam tumpukan kurang dari atau sama dengan simpul anaknya (jika ada)
(Tumpukan minimum)
3. Prinsip penyortiran heap
Penyortiran tumpukan adalah untuk mengeluarkan angka maksimum di bagian atas tumpukan maksimum, terus menyesuaikan tumpukan yang tersisa ke tumpukan maksimum, dan mengeluarkan angka maksimum di bagian atas tumpukan lagi. Proses ini berlanjut sampai hanya ada satu angka yang tersisa. Tentukan operasi berikut di tumpukan:
Max-heapify: Sesuaikan simpul ujung tumpukan sehingga simpul anak selalu lebih kecil dari node induk
Buat tumpukan maksimum (build-max-heap): ulang semua data tumpukan untuk menjadikannya tumpukan maksimum
Heap-Sort: Lepaskan simpul root dari data pertama dan lakukan operasi rekursif penyesuaian tumpukan maksimum
Sebelum melanjutkan diskusi berikut, satu masalah yang perlu dicatat adalah: array semuanya berbasis nol, yang berarti bahwa model struktur data heap kami akan berubah.
(Berbasis nol)
Sejalan dengan itu, beberapa rumus perhitungan juga harus disesuaikan sesuai:
Induk (i) = lantai ((i-1)/2), subskrip node induk dari i
Kiri (i) = 2i + 1, subskrip simpul anak kiri i
Kanan (i) = 2 (i + 1), subskrip simpul anak yang tepat dari i
Fungsi penyesuaian tumpukan max (maxheapify) adalah untuk mempertahankan sifat -sifat tumpukan terbesar dan merupakan subrutin inti untuk menciptakan tumpukan terbesar. Proses operasi ditunjukkan pada gambar:
(Max-heapify)
Karena tumpukan masih melanggar tumpukan sifat setelah satu penyesuaian, pengujian rekursif diperlukan sehingga seluruh tumpukan memenuhi sifat tumpukan. Itu dapat diekspresikan dalam JavaScript sebagai berikut:
/** * Periksa dari indeks dan pertahankan properti heap maksimum * * @Array * * Indeks awal dari pemeriksaan @Index * * @HeApsize ukuran heap * **/function maxheapify (array, index, heapsize) {var Imax = index, ileft = 2 * index + 1, iright = 2 * (indeks + 1); if (ileft <heapsize && array [index] <array [ileft]) {imax = ileft; } if (iright <heapsize && array [IMAX] <array [iright]) {iMax = iright; } if (Imax! = index) {swap (array, IMAX, index); MaxHeAPIFY (array, IMAX, Heapsize); // penyesuaian rekursif}} swap fungsi (array, i, j) {var temp = array [i]; array [i] = array [j]; array [j] = temp;}Secara umum, rekursi terutama digunakan dalam metode pembagian dan perawatan, dan tidak perlu untuk pembagian dan perawatan di sini. Selain itu, panggilan rekursif memerlukan tumpukan penekan/kliring, yang memiliki sedikit kerugian dalam kinerja dibandingkan dengan iterasi. Tentu saja, ini dapat diabaikan sesuai dengan aturan 20/80. Tetapi jika Anda berpikir menggunakan rekursi akan membuat Anda merasa tidak nyaman, Anda juga dapat menggunakan iterasi, seperti berikut:
/** * Periksa dari indeks dan pertahankan properti heap maksimum * * @Array * * Indeks awal dari pemeriksaan @Index * * @Heapsize ukuran heap * **/function maxheapify (array, index, heapsize) {var Imax, ileft, iRight; while (true) {IMAX = index; ILEFT = 2 * indeks + 1; iright = 2 * (indeks + 1); if (ileft <heapsize && array [index] <array [ileft]) {imax = ileft; } if (iright <heapsize && array [IMAX] <array [iright]) {iMax = iright; } if (Imax! = index) {swap (array, IMAX, index); indeks = IMAX; } else {break; }}} function swap (array, i, j) {var temp = array [i]; array [i] = array [j]; array [j] = temp;}Tujuan menciptakan tumpukan maksimum (build-max-heap) adalah untuk mengubah array menjadi tumpukan maksimum, menerima dua parameter array dan ukuran tumpukan. Build-Max-heap akan memanggil max-heapify dari bawah ke atas untuk mengubah array dan membangun tumpukan maksimum. Karena Max-HeAPIFy dapat memastikan bahwa node setelah bajingan saya memenuhi properti tumpukan terbesar, panggilan bottom-up untuk max-heAPIFy dapat mempertahankan properti ini selama proses transformasi. Jika elemen nomor heap maksimum adalah n, maka build-max-heap panggilan max-heapify secara berurutan dari induk (n). Prosesnya adalah sebagai berikut:
Deskripsi adalah sebagai berikut dalam JavaScript:
function buildmaxHeap (array, heapsize) {var i, iparent = math.floor ((heapsize - 1) / 2); untuk (i = iparent; i> = 0; i--) {maxheapify (array, i, heapsize); }}Heap-Sort adalah algoritma antarmuka untuk penyortiran heap. Heap-Sort First Calls Build-Max-Heap untuk mengubah array menjadi tumpukan maksimum, kemudian menukar elemen atas dan bawah tumpukan, kemudian naik ke bawah, dan akhirnya memanggil max-heapify untuk mempertahankan properti tumpukan maksimum. Karena elemen teratas dari tumpukan harus menjadi elemen terbesar dalam tumpukan, setelah satu operasi, elemen terbesar yang ada di tumpukan dipisahkan dari tumpukan dari tumpukan, dan setelah berulang N-1 kali, array diatur. Seluruh proses adalah sebagai berikut:
Deskripsi adalah sebagai berikut dalam JavaScript:
fungsi heapsort (array, heapsize) {buildmaxheap (array, heapsize); untuk (int i = heapsize-1; i> 0; i--) {swap (array, 0, i); Maxheapify (array, 0, i); }}4. Implementasi Bahasa JavaScript
Akhirnya, atur di atas menjadi kode JavaScript lengkap sebagai berikut:
function heapsort (array) {function swap (array, i, j) {var temp = array [i]; array [i] = array [j]; array [j] = temp; } function maxheapify (array, index, heapsize) {var Imax, ileft, iright; while (true) {IMAX = index; ILEFT = 2 * indeks + 1; iright = 2 * (indeks + 1); if (ileft <heapsize && array [index] <array [ileft]) {imax = ileft; } if (iright <heapsize && array [IMAX] <array [iright]) {iMax = iright; } if (Imax! = index) {swap (array, IMAX, index); indeks = IMAX; } else {break; }}} function buildmaxHeap (array) {var i, iparent = math.floor (array.length / 2) - 1; untuk (i = iparent; i> = 0; i--) {maxheapify (array, i, array.length); }} function sort (array) {buildmaxheap (array); untuk (var i = array.length-1; i> 0; i--) {swap (array, 0, i); Maxheapify (array, 0, i); } return array; } return sort (array);}5. Aplikasi Algoritma Pemilahan Hump
(1) Kinerja/kompleksitas algoritma
Kompleksitas waktu dari jenis heap sangat stabil (kita dapat melihat bahwa itu tidak sensitif terhadap data input), dan merupakan kompleksitas O (nn), kasus terbaik sama dengan kasus terburuk.
Namun, kompleksitas spasialnya bervariasi sesuai dengan implementasi. Di atas membahas dua kompleksitas umum: O (n) dan O (1). Berdasarkan prinsip ruang menghemat, saya merekomendasikan metode kompleksitas O (1).
(2) Stabilitas algoritma
Ada sejumlah besar proses penyaringan dan pemindahan dalam penyortiran tumpukan, yang termasuk dalam algoritma penyortiran yang tidak stabil.
(3) Skenario algoritma yang berlaku
Penyortiran tumpukan akan menimbulkan overhead yang relatif besar dalam proses membangun tumpukan dan menyesuaikan tumpukan, dan itu tidak berlaku ketika ada beberapa elemen. Namun, ketika ada banyak elemen, itu masih merupakan pilihan yang baik. Terutama ketika memecahkan masalah seperti "jumlah top n besar", hampir algoritma yang disukai.