Sifat heap
Tumpukan adalah pohon yang benar -benar biner, yang dapat diimplementasikan dalam kenyataan melalui array. Salah satu sifat yang paling penting adalah bahwa setiap node lebih kecil dari (lebih besar dari) sama dengan node anaknya. Tumpukan dengan simpul akar terkecil disebut tumpukan terkecil, dan tumpukan dengan simpul akar terbesar disebut tumpukan terbesar. Gambar berikut menunjukkan contoh tumpukan terbesar dan representasi arraynya, yang dapat secara intuitif terlihat bahwa setiap node lebih besar dari anak -anaknya.
Seperti dapat dilihat pada gambar di atas, node dari pohon biner yang sepenuhnya dapat diatur agar dari simpul akar nomor 1, sesuai dengan indeks dalam array a (perhatikan bahwa subskrip di sini dimulai dari 1). Diberikan simpul I, kita dapat dengan mudah mendapatkan anak kirinya adalah 2i, anak kanan adalah 2i+1, dan node induk adalah I/2
Operasi Dasar Heap
Ada dua operasi dasar untuk tumpukan (lihat tumpukan minimum sebagai contoh di bawah):
Masukkan elemen k: tambahkan k langsung ke ujung array, dan kemudian menggelembung untuk menyesuaikan heap. Operasi Bubble Up: Bandingkan elemen yang akan disesuaikan dengan simpul induknya, dan jika lebih besar dari simpul induknya, pertukarannya sampai sifat -sifat tumpukan dipulihkan.
Ekstrak nilai terbanyak: Nilai terbanyak adalah elemen root. Kemudian hapus, biarkan elemen root = elemen simpul daun terakhir, dan kemudian menggelembung dari elemen root untuk menyesuaikan heap. Operasi Bubble Down: Setiap kali, Anda harus memilih simpul anak terkecil dari tiga node untuk menyesuaikan node, yang memiliki anak kiri dan kanan untuk bertukar (jika yang terkecil, tidak perlu bertukar dirinya sendiri), sampai sifat -sifat tumpukan dipulihkan.
Dalam praktiknya, seringkali perlu membangun array yang tidak tertib yang berisi elemen N menjadi tumpukan. Konstruktor di kelas heap di bawah ini akan menunjukkan cara membangun tumpukan _Bubbledown Bubble Down Accustment. Tumpukan pada dasarnya adalah pohon yang benar -benar biner, dan tinggi pohon selalu lognlogn. Operasi yang memakan waktu dari setiap operasi dasar adalah untuk menggelegak dan menyesuaikan untuk memenuhi sifat-sifat tumpukan, sehingga kompleksitas waktu mereka adalah O (nlogn) O (nlogn).
Contoh Java:
// float public void swim (int k) {while (k/2> = 1 && less (pq [k/2], pq [k])) {exch (pq, k/2, k); k = k/2; }} // sink private void sink () {int k = 1; while (2*k <n) {int j = 2*k; if (kurang (pq [j], pq [j+1])) j ++; if (less (pq [k], pq [j])) exch (pq, k, j); Lainnya istirahat; k = j; }} Tumpukan Prinsip Implementasi Penyortiran
Itu dibagi menjadi dua langkah:
1. Atur array dalam pesanan tumpukan biner
2. Ubah posisi simpul root dan simpul terakhir, dan kemudian tenggelam node root.
menyelesaikan:
Mungkin kode saya sedikit berbeda dari animasi di atas, tetapi prinsip -prinsip dasarnya serupa.
Heapsort kelas publik memperluas Basesort {private int n; @Override public void sort (sebanding [] a) {n = a.length-1; int k = n/2; while (k> = 1) {sink (a, k); K--; } k = 1; while (k <= n) {exch (a, k, n--); wastafel (a, k); }}}