Ang isang heap ay tinutukoy bilang 'bahagyang naayos' at hindi 'bahagyang pinagsunod-sunod.' Ang salitang 'pag-uuri' ay nangangahulugang kumpletong pagkakasunud-sunod (kumpletong pag-uuri). Ang isang heap ay hindi bahagyang inayos nang basta-basta. Ang isang heap ay bahagyang inayos ayon sa isang criterion (pattern), tulad ng ipinapakita sa ibaba.
Kaya, ang heapsort ay binubuo ng dalawang yugto: pagbuo ng heap at pagkuha ng nakaayos na elemento mula sa tuktok ng heap. Sa ikalawang yugto, pagkatapos ng bawat pagkuha, ang bunton ay itinayong muli. Ang bawat muling pagtatayo ay mas mabilis kaysa sa orihinal na proseso ng pagbuo dahil ang muling pagtatayo ay ginawa mula sa isang nakaraang build, kung saan ang isang elemento ay inalis. At kasama niyan, ang heapsort ay nag-uuri ng isang ganap na hindi naayos na listahan.
Ang layunin ng artikulong ito ay maikling ipaliwanag ang heapsort at pagkatapos ay gawin ang pagiging kumplikado ng oras nito (tingnan ang kahulugan ng pagiging kumplikado ng oras sa ibaba). Sa pagtatapos, ang coding ay ginagawa sa C++.
Pinakamababang Bunton
Ang isang heap ay maaaring isang minimum na heap o isang maximum na heap. Ang max-heap ay isa kung saan ang unang elemento ay ang pinakamataas na elemento, at ang buong puno o katumbas na listahan ay bahagyang nakaayos sa pababang pagkakasunud-sunod. Ang min-heap ay isa kung saan ang unang elemento ay ang pinakamaliit na elemento, at ang buong listahan ay bahagyang nakaayos sa pataas na pagkakasunud-sunod. Sa artikulong ito, ang pinakamababang heap lamang ang isinasaalang-alang. Tandaan: sa paksa ng heap, ang isang elemento ay tinatawag ding node.
Ang isang bunton ay isang kumpletong binary tree. Ang binary tree ay maaaring ipahayag bilang isang array (listahan); basahin mula sa itaas hanggang sa ibaba at kaliwa hanggang kanan. Ang heap property para sa isang min-heap ay ang isang parent node ay mas mababa o katumbas ng bawat isa sa dalawang anak nito. Ang isang halimbawa ng isang hindi nakaayos na listahan ay:
| 9 | 19 | 24 | 5 | 3 | labing-isa | 14 | 22 | 7 | 6 | 17 | labinlima | wala | wala | wala |
| 0 | 1 | dalawa | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | labing-isa | 12 | 13 | 14 |
Ang unang hilera ng talahanayang ito ay ang mga elemento ng array. Sa pangalawang hilera ay ang mga zero-based na index. Ang listahang ito ng mga elemento ay maaaring ipahayag bilang isang puno. Ang mga null na elemento ay idinagdag upang makagawa ng isang buong binary tree. Sa mahigpit na pagsasalita, ang mga null na elemento ay hindi bahagi ng listahan (puno). Walang pagkakasunud-sunod ang listahang ito, kaya hindi pa ito isang tambak. Ito ay magiging isang tambak kapag ito ay nagkaroon ng bahagyang pagkakasunud-sunod, ayon sa heap property.
Relasyon sa Pagitan ng mga Node at Index
Tandaan, ang heap ay isang kumpletong binary tree bago magkaroon ng heap configuration (heap property). Ang nakaraang listahan ay hindi pa isang heap, dahil ang mga elemento ay hindi sumusunod sa heap property. Ito ay nagiging isang heap pagkatapos muling ayusin ang mga elemento sa bahagyang pagkakasunud-sunod ayon sa min-heap property. Ang bahagyang pagkakasunud-sunod ay makikita bilang bahagyang pag-uuri (bagama't ang salitang 'pag-uuri' ay nangangahulugang kumpletong pagkakasunud-sunod).
Kung ang isang binary tree ay isang bunton o hindi, ang bawat magulang ay may dalawang anak, maliban sa mga dahon (huling) node. May kaugnayang matematikal sa mga index sa pagitan ng bawat magulang at mga anak nito. Ito ay ang mga sumusunod: Kung ang magulang ay nasa index i, ang kaliwang anak ay nasa index:
dalawa * i + 1at ang tamang bata ay nasa index:
dalawa * i + dalawaIto ay para sa zero-based na pag-index. Kaya, ang isang magulang sa index 0 ay may kaliwang anak nito sa index 2×0+1=1 at ang kanang anak nito sa 2×0+2=2. Ang isang magulang sa index 1 ay may kaliwang anak nito sa index 2×1+1=3 at kanang anak sa index 2×1+2=4; at iba pa.
Sa pamamagitan ng min-heap property, ang magulang sa i ay mas mababa o katumbas ng kaliwang anak sa 2i+1 at mas mababa sa o katumbas ng kanang anak sa 2i+2.
Bunton
Ang ibig sabihin ng heapifying ay pagbuo ng isang tambak. Nangangahulugan itong muling ayusin ang mga elemento ng isang listahan (o kaukulang puno) upang masiyahan ang mga ito sa heap property. Sa pagtatapos ng proseso ng heapifying, ang listahan o puno ay isang heap.
Kung ang nakaraang hindi na-sort na listahan ay naipon, ito ay magiging:
| 3 | 5 | labing-isa | 7 | 6 | labinlima | 14 | 22 | 9 | 19 | 17 | 24 | wala | wala | wala |
| 0 | 1 | dalawa | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | labing-isa | 12 | 13 | 14 |
Tandaan: mayroong 12 elemento at hindi 15 sa listahan. Sa pangalawang hilera ay ang mga index. Sa proseso ng heap building, kailangang suriin ang mga elemento, at ang ilan ay ipinagpalit.
Pansinin na ang pinakamaliit at unang elemento ay 3. Ang natitira sa mga elemento ay sumusunod sa isang pataas ngunit alun-alon na paraan. Kung ang kaliwa at kanang mga bata sa mga posisyong 2i+1 at 2i+2 ay mas malaki sa o katumbas ng magulang sa i, kung gayon ito ay isang min-heap. Hindi ito ganap na pag-aayos o pag-uuri. Ito ay bahagyang pag-order, ayon sa heap property. Dito magsisimula ang susunod na yugto para sa heap sort.
Heapify Time Complexity
Ang pagiging kumplikado ng oras ay ang kaugnay na oras ng pagpapatakbo ng ilang code. Ito ay makikita bilang ang bilang ng mga pangunahing operasyon para makumpleto ang code na iyon. Mayroong iba't ibang mga algorithm para sa heap building. Ang pinakamabisa at pinakamabilis na patuloy na hatiin ang listahan sa dalawa, sinusuri ang mga elemento mula sa ibaba, at pagkatapos ay gumagawa ng ilang pagpapalit ng mga elemento. Hayaang N ang bilang ng mga praktikal na elemento sa listahan. Sa algorithm na ito, ang maximum na bilang ng mga pangunahing operasyon (pagpapalit) ay N. Ang pagiging kumplikado ng oras para sa heapifying ay ibinibigay dati bilang:
O ( n )Kung saan ang n ay N at ang pinakamataas na posibleng bilang ng mga pangunahing operasyon. Ang notasyong ito ay tinatawag na Big-O notation. Nagsisimula ito sa O sa malalaking titik, na sinusundan ng mga panaklong. Sa loob ng mga panaklong ay ang expression para sa posibleng pinakamataas na bilang ng mga operasyon.
Tandaan: ang pagdaragdag ay maaaring maging multiplikasyon kung ang parehong bagay na idinaragdag ay paulit-ulit.
Ilustrasyon ng Heapsort
Ang nakaraang hindi na-sort na listahan ay gagamitin upang ilarawan ang heapsort. Ang ibinigay na listahan ay:
9 19 24 5 3 labing-isa 14 22 7 6 17 labinlimaAng min-heap na ginawa mula sa listahan ay:
3 5 labing-isa 7 6 labinlima 14 22 9 19 17 24Ang unang yugto sa heapsort ay ang paggawa ng heap na ginawa. Ito ay isang bahagyang nakaayos na listahan. Ito ay hindi isang pinagsunod-sunod (ganap na pinagsunod-sunod) na listahan.
Ang pangalawang yugto ay binubuo ng pag-alis ng pinakamaliit na elemento, na siyang unang elemento, mula sa heap, muling pag-heap sa natitirang heap, at pag-alis ng pinakamaliit na elemento sa mga resulta. Ang pinakamaliit na elemento ay palaging ang unang elemento sa re-heapifyied heap. Ang mga elemento ay hindi tinanggal at itinapon. Maaari silang ipadala sa ibang array sa pagkakasunud-sunod kung saan sila aalisin.
Sa huli, ang bagong array ay magkakaroon ng lahat ng mga elemento na pinagsunod-sunod (ganap), sa pataas na pagkakasunud-sunod; at hindi na partially order lang.
Sa pangalawang yugto, ang unang bagay na dapat gawin ay alisin ang 3 at ilagay ito sa bagong array. Ang mga resulta ay:
3at
5 labing-isa 7 6 labinlima 14 22 9 19 17 24Ang natitirang mga elemento ay kailangang i-heapified bago makuha ang unang elemento. Ang tambak ng natitirang mga elemento ay maaaring maging:
5 6 7 9 labinlima 14 22 labing-isa 19 17 24Ang pag-extract ng 5 at pagdaragdag sa bagong listahan (array) ay nagbibigay ng mga resulta:
3 5at
6 7 9 labinlima 14 22 labing-isa 19 17 24Ang pagpaparami sa natitirang hanay ay magbibigay ng:
6 7 9 labinlima 14 22 labing-isa 19 17 24Ang pag-extract ng 6 at pagdaragdag sa bagong listahan (array) ay nagbibigay ng mga resulta:
3 5 6at
7 9 labinlima 14 22 labing-isa 19 17 24Ang pagpaparami sa natitirang hanay ay magbibigay ng:
7 9 labing-isa 14 22 labinlima 19 17 24Ang pag-extract ng 7 at pagdaragdag nito sa bagong listahan ay nagbibigay ng mga resulta:
3 5 6 7at
9 labing-isa 14 22 labinlima 19 17 24Ang pagpaparami sa natitirang hanay ay nagbibigay ng:
9 labing-isa 14 22 labinlima 19 17 24Ang pag-extract ng 9 at pagdaragdag sa bagong listahan, ay nagbibigay ng mga resulta:
3 5 6 7 9at
labing-isa 14 22 labinlima 19 17 24Ang pagpaparami sa natitirang hanay ay nagbibigay ng:
labing-isa 14 17 labinlima 19 22 24Ang pag-extract ng 11 at pagdaragdag nito sa bagong listahan ay nagbibigay ng mga resulta:
3 5 6 7 9 labing-isaat
14 17 labinlima 19 22 24Ang pagpaparami sa natitirang hanay ay magbibigay ng:
14 17 labinlima 19 22 24Ang pag-extract ng 14 at pagdaragdag nito sa bagong listahan ay nagbibigay ng mga resulta:
3 5 6 7 9 labing-isa 14at
17 labinlima 19 22 24Ang pagpaparami sa natitirang hanay ay magbibigay ng:
labinlima 17 19 22 24Ang pag-extract ng 15 at pagdaragdag nito sa bagong listahan ay nagbibigay ng mga resulta:
3 5 6 7 9 labing-isa 14 labinlimaat
17 19 22 24Ang pagpaparami sa natitirang hanay ay magbibigay ng:
17 19 22 24Ang pag-extract ng 17 at pagdaragdag nito sa bagong listahan ay nagbibigay ng mga resulta:
3 5 6 7 9 labing-isa 14 labinlima 17at
19 22 24Ang pagpaparami sa natitirang hanay ay magbibigay ng:
19 22 24Ang pag-extract ng 19 at pagdaragdag nito sa bagong listahan ay nagbibigay ng mga resulta:
3 5 6 7 9 labing-isa 14 labinlima 17 19at
22 24Ang pagpaparami sa natitirang hanay ay nagbibigay ng:
22 24Ang pag-extract ng 22 at pagdaragdag nito sa bagong listahan ay nagbibigay ng mga resulta:
3 5 6 7 9 labing-isa 14 labinlima 17 19 22at
24Ang pagpaparami sa natitirang hanay ay nagbibigay ng:
24Ang pag-extract ng 24 at pagdaragdag nito sa bagong listahan ay nagbibigay ng mga resulta:
3 5 6 7 9 labing-isa 14 labinlima 17 19 22 24at
- - -Wala nang laman ang heap array. Ang lahat ng mga elemento na mayroon ito sa simula ay nasa bagong array (listahan) at pinagsunod-sunod.
Heapsort Algorithm
Bagama't maaaring nabasa ng mambabasa sa mga textbook na ang heapsort ay binubuo ng dalawang yugto, makikita pa rin ang heapsort na binubuo ng isang yugto, na paulit-ulit na lumiliit sa ibinigay na array. Sa pamamagitan nito, ang algorithm upang ayusin sa heapsort ay ang mga sumusunod:
- Palakihin ang hindi naayos na listahan.
- I-extract ang unang elemento ng heap at ilagay ito bilang unang elemento ng bagong listahan.
- Palakihin ang natitirang listahan.
- I-extract ang unang elemento ng bagong heap at ilagay bilang susunod na elemento ng bagong listahan.
- Ulitin ang mga nakaraang hakbang sa pagkakasunud-sunod hanggang sa walang laman ang listahan ng heap. Sa huli, ang bagong listahan ay pinagsunod-sunod.
Wastong Pagiging Kumplikado ng Oras ng Heapsort
Ang one-stage na diskarte ay ginagamit upang matukoy ang pagiging kumplikado ng oras para sa heapsort. Ipagpalagay na mayroong 8 unsorted na elemento na pag-uuri-uriin.
Ang posibleng maximum na bilang ng mga pagpapatakbo upang palakihin ang 8 mga elemento ay 8 .Ang posibleng maximum na bilang ng mga operasyon upang palakihin ang natitira 7 mga elemento ay 7 .
Ang posibleng maximum na bilang ng mga operasyon upang palakihin ang natitira 6 mga elemento ay 6 .
Ang posibleng maximum na bilang ng mga operasyon upang palakihin ang natitira 5 mga elemento ay 5 .
Ang posibleng maximum na bilang ng mga operasyon upang palakihin ang natitira 4 mga elemento ay 4 .
Ang posibleng maximum na bilang ng mga operasyon upang palakihin ang natitira 3 mga elemento ay 3 .
Ang posibleng maximum na bilang ng mga operasyon upang palakihin ang natitira dalawa mga elemento ay dalawa .
Ang posibleng maximum na bilang ng mga operasyon upang palakihin ang natitira 1 elemento ay 1 .
Ang posibleng maximum na bilang ng mga operasyon ay:
8 + 7 + 6 + 5 + 4 + 3 + dalawa + 1 = 36Ang average ng mga bilang ng mga operasyon ay:
36 / 8 = 4.5Pansinin na ang huling apat na tambak sa nakaraang ilustrasyon ay hindi nagbago, nang ang unang elemento ay inalis. Ang ilan sa mga naunang tambak ay hindi rin nagbago noong inalis ang unang elemento. Sa pamamagitan nito, ang isang mas mahusay na average na bilang ng mga pangunahing operasyon (pagpapalit) ay 3 at hindi 4.5. Kaya, ang isang mas mahusay na kabuuang average na bilang ng mga pangunahing operasyon ay:
24 = 8 x 3=> 24 = 8 x log < sub > dalawa < / sub > 8
mula noong log dalawa 8 = 3.
Sa pangkalahatan, ang average na pagiging kumplikado ng oras ng kaso para sa heapsort ay:
O ( n. log2n )Kung saan ang tuldok ay nangangahulugang multiplikasyon at n ay N, ang kabuuang bilang ng mga elemento sa listahan (alinman sa listahan).
Tandaan na ang pagpapatakbo ng pagkuha ng unang elemento ay hindi pinansin. Sa paksa ng Time Complexity, ang mga operasyon na medyo maikli ang oras ay binabalewala.
Pag-coding sa C++
Sa library ng algorithm ng C++, mayroong function na make_heap(). Ang syntax ay:
template < klase RandomAccessIterator, klase Ikumpara >constexpr walang bisa gumawa_bunton ( RandomAccessIterator muna, RandomAccessIterator ang huli, Compare comp ) ;
Ito ay tumatagal ng iterator na tumuturo sa unang elemento ng isang vector bilang ang unang argumento at pagkatapos ay ang iterator na tumuturo sa kabila lamang ng dulo ng vector bilang ang huling argumento nito. Para sa nakaraang unsorted na listahan, ang syntax ay gagamitin bilang mga sumusunod upang makakuha ng minimum na heap:
vector < int > vtr = { 9 , 19 , 24 , 5 , 3 , labing-isa , 14 , 22 , 7 , 6 , 17 , labinlima } ;vector < int > :: umuulit iterB = vtr. magsimula ( ) ;
vector < int > :: umuulit iterE = vtr. wakas ( ) ;
gumawa_bunton ( iterB, iterE, mas malaki < int > ( ) ) ;
Binabago ng code na ito ang isang nilalaman ng vector sa isang minimum na configuration ng heap. Sa mga sumusunod na C++ vector, dalawang vector ang gagamitin sa halip na dalawang array.
Upang kopyahin at ibalik ang unang elemento ng isang vector, gamitin ang vector syntax:
constexpr sanggunian sa harap ( ) ;Upang alisin ang unang elemento ng isang vector at itapon ito, gamitin ang vector syntax:
constexpr pagbubura ng iterator ( posisyon ng const_iterator )Upang magdagdag ng elemento sa likod ng isang vector (susunod na elemento), gamitin ang vector syntax:
constexpr walang bisa push_back ( const T at x ) ;Ang simula ng programa ay:
#include#include
#include
gamit namespace std ;
Kasama ang algorithm at vector library. Susunod sa programa ay ang heapsort() function, na:
walang bisa heapsort ( vector < int > at oldV, vector < int > at bagoV ) {kung ( matandaV. laki ( ) > 0 ) {
vector < int > :: umuulit iterB = matandaV. magsimula ( ) ;
vector < int > :: umuulit iterE = matandaV. wakas ( ) ;
gumawa_bunton ( iterB, iterE, mas malaki < int > ( ) ) ;
int susunod = matandaV. harap ( ) ;
matandaV. burahin ( iterB ) ;
bagoV. push_back ( susunod ) ;
heapsort ( lumangV, bagoV ) ;
}
}
Ito ay isang recursive function. Ginagamit nito ang make_heap() function ng C++ algorithm library. Kinukuha ng pangalawang segment ng code sa kahulugan ng function ang unang elemento mula sa lumang vector pagkatapos ng heap building at idinaragdag bilang susunod na elemento para sa bagong vector. Tandaan na sa kahulugan ng function, ang mga parameter ng vector ay mga sanggunian, habang ang function ay tinatawag na may mga identifier (mga pangalan).
Ang isang angkop na pangunahing pag-andar ng C++ para dito ay:
int pangunahing ( int argc, char ** argv ){
vector < int > matandaV = { 9 , 19 , 24 , 5 , 3 , labing-isa , 14 , 22 , 7 , 6 , 17 , labinlima } ;
vector < int > bagoV ;
heapsort ( lumangV, bagoV ) ;
para sa ( int i = 0 ; i < bagoV. laki ( ) ; i ++ ) {
cout << bagoV [ i ] << '' ;
}
cout << endl ;
bumalik 0 ;
}
Ang output ay:
3 5 6 7 9 labing-isa 14 labinlima 17 19 22 24pinagsunod-sunod (ganap).
Konklusyon
Detalyadong tinalakay ng artikulo ang katangian at paggana ng Heap Sort na karaniwang kilala bilang Heapsort, bilang isang algorithm ng pag-uuri. Ang Heapify Time Complexity, Heapsort illustration, at Heapsort bilang isang algorithm ay sakop at sinusuportahan ng mga halimbawa. Ang average na pagiging kumplikado ng oras para sa isang mahusay na pagkakasulat na programa ng heapsort ay O(nlog(n))