Timbunan dirujuk sebagai 'disusun sebahagian' dan bukan 'diisih sebahagian'. Perkataan 'isih' bermaksud susunan lengkap (isih lengkap). Timbunan tidak dipesan sebahagiannya sewenang-wenangnya. Timbunan sebahagiannya disusun mengikut kriteria (corak), seperti yang ditunjukkan di bawah.
Jadi, heapsort terdiri daripada dua peringkat: membina timbunan dan mengekstrak elemen tersusun dari bahagian atas timbunan. Pada peringkat kedua, selepas setiap pengekstrakan, timbunan itu dibina semula. Setiap pembinaan semula adalah lebih pantas daripada proses pembinaan asal kerana pembinaan semula dilakukan daripada binaan sebelumnya, di mana satu elemen telah dialih keluar. Dan dengan itu, heapsort mengisih senarai yang tidak diisih sepenuhnya.
Matlamat artikel ini adalah untuk menerangkan secara ringkas heapsort dan kemudian menghasilkan kerumitan masanya (lihat maksud kerumitan masa di bawah). Pada penghujungnya, pengekodan dilakukan dalam C++.
Timbunan Minimum
Timbunan boleh menjadi timbunan minimum atau timbunan maksimum. Timbunan maks ialah elemen pertama yang merupakan elemen tertinggi, dan keseluruhan pepohon atau senarai yang sepadan sebahagiannya disusun mengikut tertib menurun. Timbunan min ialah elemen di mana elemen pertama ialah elemen terkecil, dan keseluruhan senarai disusun separa dalam tertib menaik. Dalam artikel ini, hanya timbunan minimum yang dipertimbangkan. Nota: dalam topik timbunan, elemen juga dipanggil nod.
Timbunan ialah pokok binari yang lengkap. Pokok binari boleh dinyatakan sebagai tatasusunan (senarai); baca dari atas ke bawah dan kiri ke kanan. Sifat timbunan untuk timbunan min ialah nod induk adalah kurang daripada atau sama dengan setiap dua anaknya. Contoh senarai tidak tertib ialah:
| 9 | 19 | 24 | 5 | 3 | sebelas | 14 | 22 | 7 | 6 | 17 | lima belas | null | null | null |
| 0 | 1 | dua | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | sebelas | 12 | 13 | 14 |
Baris pertama jadual ini ialah elemen tatasusunan. Di baris kedua ialah indeks berasaskan sifar. Senarai unsur ini boleh dinyatakan sebagai pokok. Unsur nol telah ditambah untuk membuat pokok binari penuh. Tegasnya, unsur nol bukan sebahagian daripada senarai (pokok). Senarai ini tidak mempunyai susunan, jadi ia bukan satu timbunan lagi. Ia akan menjadi timbunan apabila ia mempunyai pesanan separa, mengikut sifat timbunan.
Hubungan Antara Nod dan Indeks
Ingat, timbunan ialah pokok binari yang lengkap sebelum mempunyai konfigurasi timbunan (harta timbunan). Senarai sebelumnya bukan timbunan lagi, kerana unsur-unsur tidak mematuhi sifat timbunan. Ia menjadi timbunan selepas menyusun semula elemen ke dalam susunan separa mengikut sifat timbunan min. Susunan separa boleh dilihat sebagai isihan separa (walaupun perkataan 'isih' bermaksud susunan lengkap).
Sama ada pokok binari adalah timbunan atau tidak, setiap ibu bapa mempunyai dua anak, kecuali nod daun (terakhir). Terdapat hubungan matematik antara indeks antara setiap ibu bapa dan anak-anaknya. Ia adalah seperti berikut: Jika ibu bapa berada pada indeks i, maka anak kiri berada pada indeks:
dua * i + 1dan anak yang betul berada di indeks:
dua * i + duaIni adalah untuk pengindeksan berasaskan sifar. Oleh itu, ibu bapa pada indeks 0 mempunyai anak kirinya pada indeks 2×0+1=1 dan anak kanannya pada 2×0+2=2. Ibu bapa pada indeks 1 mempunyai anak kirinya pada indeks 2×1+1=3 dan anak kanan pada indeks 2×1+2=4; dan sebagainya.
Dengan sifat timbunan min, ibu bapa di i adalah kurang daripada atau sama dengan anak kiri pada 2i+1 dan kurang daripada atau sama dengan anak kanan pada 2i+2.
Timbunan
Menimbun bermaksud membina timbunan. Ia bermaksud untuk menyusun semula elemen senarai (atau pokok yang sepadan) supaya ia memenuhi sifat timbunan. Pada penghujung proses penimbunan, senarai atau pokok ialah timbunan.
Jika senarai tidak diisih sebelumnya ditimbun, ia akan menjadi:
| 3 | 5 | sebelas | 7 | 6 | lima belas | 14 | 22 | 9 | 19 | 17 | 24 | null | null | null |
| 0 | 1 | dua | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | sebelas | 12 | 13 | 14 |
Nota: terdapat 12 elemen dan bukan 15 dalam senarai. Di baris kedua ialah indeks. Dalam proses pembinaan timbunan, elemen perlu diperiksa, dan beberapa ditukar.
Perhatikan bahawa unsur terkecil dan pertama ialah 3. Selebihnya unsur mengikuti dengan cara menaik tetapi beralun. Jika anak kiri dan kanan pada kedudukan 2i+1 dan 2i+2 masing-masing lebih besar daripada atau sama dengan induk di i, maka ini ialah timbunan min. Ini bukan pesanan atau pengisihan penuh. Ini adalah pesanan separa, mengikut sifat timbunan. Dari sinilah peringkat seterusnya untuk jenis timbunan bermula.
Kerumitan Masa Heapify
Kerumitan masa ialah masa berjalan relatif bagi sesetengah kod. Ia boleh dilihat sebagai bilangan operasi utama untuk kod itu selesai. Terdapat algoritma yang berbeza untuk membina timbunan. Yang paling cekap dan terpantas terus membahagikan senarai dengan dua, menyemak elemen dari bawah, dan kemudian melakukan beberapa pertukaran elemen. Biarkan N ialah bilangan elemen praktikal dalam senarai. Dengan algoritma ini, bilangan maksimum operasi utama (swapping) ialah N. Kerumitan masa untuk penimbunan diberikan dahulu sebagai:
O ( n )Di mana n ialah N dan ialah bilangan maksimum operasi utama yang mungkin. Notasi ini dipanggil notasi Big-O. Ia bermula dengan O dalam huruf besar, diikuti dengan kurungan. Di dalam kurungan terdapat ungkapan untuk bilangan operasi tertinggi yang mungkin.
Ingat: penambahan boleh menjadi pendaraban jika perkara yang sama ditambah terus berulang.
Ilustrasi Heapsort
Senarai tidak diisih sebelumnya akan digunakan untuk menggambarkan heapsort. Senarai yang diberikan ialah:
9 19 24 5 3 sebelas 14 22 7 6 17 lima belasTimbunan min yang dihasilkan daripada senarai ialah:
3 5 sebelas 7 6 lima belas 14 22 9 19 17 24Peringkat pertama dalam heapsort ialah menghasilkan heap yang telah dihasilkan. Ini ialah senarai tertib separa. Ia bukan senarai yang diisih (diisih sepenuhnya).
Peringkat kedua terdiri daripada mengalih keluar elemen terkecil, iaitu elemen pertama, daripada timbunan, menimbun semula timbunan yang tinggal dan mengalih keluar elemen terkecil dalam hasil. Unsur yang paling sedikit sentiasa menjadi elemen pertama dalam timbunan yang ditimbun semula. Unsur-unsur tidak dibuang dan dibuang. Ia boleh dihantar ke tatasusunan yang berbeza mengikut urutan ia dialih keluar.
Pada akhirnya, tatasusunan baharu akan mempunyai semua elemen diisih (sepenuhnya), dalam susunan menaik; dan tidak lagi hanya sebahagiannya dipesan.
Pada peringkat kedua, perkara pertama yang perlu dilakukan ialah mengeluarkan 3 dan meletakkannya dalam tatasusunan baharu. Hasilnya ialah:
3dan
5 sebelas 7 6 lima belas 14 22 9 19 17 24Unsur yang selebihnya perlu ditimbun sebelum unsur pertama diekstrak. Timbunan elemen yang tinggal boleh menjadi:
5 6 7 9 lima belas 14 22 sebelas 19 17 24Mengekstrak 5 dan menambah senarai baharu (array) memberikan keputusan:
3 5dan
6 7 9 lima belas 14 22 sebelas 19 17 24Menimbun set yang tinggal akan memberikan:
6 7 9 lima belas 14 22 sebelas 19 17 24Mengekstrak 6 dan menambah senarai baharu (array) memberikan hasil:
3 5 6dan
7 9 lima belas 14 22 sebelas 19 17 24Menimbun set yang tinggal akan memberikan:
7 9 sebelas 14 22 lima belas 19 17 24Mengekstrak 7 dan menambahkannya ke senarai baharu memberikan hasil:
3 5 6 7dan
9 sebelas 14 22 lima belas 19 17 24Menimbun set yang tinggal memberikan:
9 sebelas 14 22 lima belas 19 17 24Mengekstrak 9 dan menambah senarai baharu, memberikan keputusan:
3 5 6 7 9dan
sebelas 14 22 lima belas 19 17 24Menimbun set yang tinggal memberikan:
sebelas 14 17 lima belas 19 22 24Mengekstrak 11 dan menambahkannya ke senarai baharu memberikan hasil:
3 5 6 7 9 sebelasdan
14 17 lima belas 19 22 24Menimbun set yang tinggal akan memberikan:
14 17 lima belas 19 22 24Mengekstrak 14 dan menambahkannya ke senarai baharu memberikan keputusan:
3 5 6 7 9 sebelas 14dan
17 lima belas 19 22 24Menimbun set yang tinggal akan memberikan:
lima belas 17 19 22 24Mengekstrak 15 dan menambahkannya ke senarai baharu memberikan hasil:
3 5 6 7 9 sebelas 14 lima belasdan
17 19 22 24Menimbun set yang tinggal akan memberikan:
17 19 22 24Mengekstrak 17 dan menambahkannya ke senarai baharu memberikan keputusan:
3 5 6 7 9 sebelas 14 lima belas 17dan
19 22 24Menimbun set yang tinggal akan memberikan:
19 22 24Mengekstrak 19 dan menambahkannya ke senarai baharu memberikan hasil:
3 5 6 7 9 sebelas 14 lima belas 17 19dan
22 24Menimbun set yang tinggal memberikan:
22 24Mengekstrak 22 dan menambahkannya ke senarai baharu memberikan keputusan:
3 5 6 7 9 sebelas 14 lima belas 17 19 22dan
24Menimbun set yang tinggal memberikan:
24Mengekstrak 24 dan menambahkannya ke senarai baharu memberikan keputusan:
3 5 6 7 9 sebelas 14 lima belas 17 19 22 24dan
- - -Tatasusunan timbunan kini kosong. Semua elemen yang ada pada mulanya kini dalam tatasusunan (senarai) baharu dan diisih.
Algoritma Heapsort
Walaupun pembaca mungkin telah membaca dalam buku teks bahawa heapsort terdiri daripada dua peringkat, heapsort masih boleh dilihat sebagai terdiri daripada satu peringkat, yang secara berulang mengecut daripada tatasusunan yang diberikan. Dengan itu, algoritma untuk mengisih dengan heapsort adalah seperti berikut:
- Timbunkan senarai yang tidak diisih.
- Ekstrak elemen pertama timbunan dan letakkannya sebagai elemen pertama senarai baharu.
- Timbunkan senarai yang tinggal.
- Ekstrak elemen pertama timbunan baharu dan letakkan sebagai elemen seterusnya senarai baharu.
- Ulangi langkah sebelumnya mengikut urutan sehingga senarai timbunan kosong. Pada akhirnya, senarai baharu diisih.
Kerumitan Masa Heapsort Betul
Pendekatan satu peringkat digunakan untuk menentukan kerumitan masa untuk heapsort. Andaikan terdapat 8 elemen yang tidak diisih untuk diisih.
Bilangan maksimum operasi yang mungkin untuk menimbun 8 unsur ialah 8 .The bilangan maksimum operasi yang mungkin untuk menimbun baki 7 unsur ialah 7 .
The bilangan maksimum operasi yang mungkin untuk menimbun baki 6 unsur ialah 6 .
The bilangan maksimum operasi yang mungkin untuk menimbun baki 5 unsur ialah 5 .
The bilangan maksimum operasi yang mungkin untuk menimbun baki 4 unsur ialah 4 .
The bilangan maksimum operasi yang mungkin untuk menimbun baki 3 unsur ialah 3 .
The bilangan maksimum operasi yang mungkin untuk menimbun baki dua unsur ialah dua .
The bilangan maksimum operasi yang mungkin untuk menimbun baki 1 unsur ialah 1 .
Bilangan maksimum operasi yang mungkin adalah:
8 + 7 + 6 + 5 + 4 + 3 + dua + 1 = 36Purata bilangan operasi ini ialah:
36 / 8 = 4.5Perhatikan bahawa empat timbunan terakhir dalam ilustrasi sebelumnya tidak berubah, apabila elemen pertama dialih keluar. Beberapa timbunan sebelumnya juga tidak berubah apabila elemen pertama dialih keluar. Dengan itu, purata bilangan operasi utama (swapping) yang lebih baik ialah 3 dan bukan 4.5. Jadi, jumlah purata bilangan operasi utama yang lebih baik ialah:
24 = 8 x 3=> 24 = 8 x log < sub > dua < / sub > 8
sejak log dua 8 = 3.
Secara umum, purata kerumitan masa kes untuk heapsort ialah:
O ( n. log2n )Di mana titik bermaksud pendaraban dan n ialah N, jumlah bilangan elemen dalam senarai (sama ada senarai).
Ambil perhatian bahawa operasi mengekstrak elemen pertama telah diabaikan. Mengenai topik Kerumitan Masa, operasi yang mengambil masa yang agak singkat diabaikan.
Pengekodan dalam C++
Dalam perpustakaan algoritma C++, terdapat fungsi make_heap(). Sintaksnya ialah:
templat < kelas RandomAccessIterator, kelas Bandingkan >konstexpr batal buat_timbunan ( RandomAccessIterator dahulu, RandomAccessIterator terakhir, Bandingkan comp ) ;
Ia mengambil iterator menunjuk ke elemen pertama vektor sebagai hujah pertamanya dan kemudian iterator menunjuk tepat di luar hujung vektor sebagai hujah terakhirnya. Untuk senarai tidak diisih sebelumnya, sintaks akan digunakan seperti berikut untuk mendapatkan timbunan minimum:
vektor < int > vtr = { 9 , 19 , 24 , 5 , 3 , sebelas , 14 , 22 , 7 , 6 , 17 , lima belas } ;vektor < int > :: iterator iterB = vtr. bermula ( ) ;
vektor < int > :: iterator iterE = vtr. tamat ( ) ;
buat_timbunan ( iterB, iterE, lebih besar < int > ( ) ) ;
Kod ini menukar kandungan vektor kepada konfigurasi timbunan minimum. Dalam vektor C++ berikut, dua vektor akan digunakan dan bukannya dua tatasusunan.
Untuk menyalin dan mengembalikan elemen pertama vektor, gunakan sintaks vektor:
konstexpr hadapan rujukan ( ) ;Untuk mengalih keluar elemen pertama vektor dan membuangnya, gunakan sintaks vektor:
konstexpr pemadam lelaran ( kedudukan const_iterator )Untuk menambah elemen di belakang vektor (elemen seterusnya), gunakan sintaks vektor:
konstexpr batal menolak kembali ( const T & x ) ;Permulaan program ialah:
#include#include
#include
menggunakan ruang nama std ;
Algoritma dan perpustakaan vektor disertakan. Seterusnya dalam program ini ialah fungsi heapsort(), iaitu:
batal heapsort ( vektor < int > & oldV, vektor < int > & baruV ) {jika ( lamaV. saiz ( ) > 0 ) {
vektor < int > :: iterator iterB = lamaV. bermula ( ) ;
vektor < int > :: iterator iterE = lamaV. tamat ( ) ;
buat_timbunan ( iterB, iterE, lebih besar < int > ( ) ) ;
int seterusnya = lamaV. hadapan ( ) ;
lamaV. memadam ( iterB ) ;
baruV. menolak kembali ( seterusnya ) ;
heapsort ( lamaV, baharuV ) ;
}
}
Ia adalah fungsi rekursif. Ia menggunakan fungsi make_heap() pustaka algoritma C++. Segmen kod kedua dalam definisi fungsi mengekstrak elemen pertama daripada vektor lama selepas bangunan timbunan dan menambah sebagai elemen seterusnya untuk vektor baharu. Ambil perhatian bahawa dalam definisi fungsi, parameter vektor adalah rujukan, manakala fungsi dipanggil dengan pengecam (nama).
Fungsi utama C++ yang sesuai untuk ini ialah:
int utama ( int argc, char ** argv ){
vektor < int > lamaV = { 9 , 19 , 24 , 5 , 3 , sebelas , 14 , 22 , 7 , 6 , 17 , lima belas } ;
vektor < int > baruV ;
heapsort ( lamaV, baharuV ) ;
untuk ( int i = 0 ; i < baruV. saiz ( ) ; i ++ ) {
cout << baruV [ i ] << '' ;
}
cout << endl ;
kembali 0 ;
}
Outputnya ialah:
3 5 6 7 9 sebelas 14 lima belas 17 19 22 24disusun (sepenuhnya).
Kesimpulan
Artikel tersebut membincangkan secara terperinci sifat dan fungsi Heap Sort yang biasanya dikenali sebagai Heapsort, sebagai algoritma pengisihan. Kerumitan Masa Heapify, ilustrasi Heapsort dan Heapsort sebagai algoritma dilindungi dan disokong oleh contoh. Purata kerumitan masa untuk program heapsort yang ditulis dengan baik ialah O(nlog(n))