Heapsort laika sarežģītība

Kaudze tiek saukta par “daļēji sakārtotu”, nevis “daļēji sakārtotu”. Vārds “šķirot” nozīmē pilnīgu sakārtošanu (pilnīgu šķirošanu). Kaudze netiek daļēji pasūtīta patvaļīgi. Kaudze ir daļēji sakārtota pēc kritērija (raksta), kā parādīts tālāk.

Tātad kaudzes šķirošana sastāv no diviem posmiem: kaudzes izveidošana un sakārtotā elementa izvilkšana no kaudzes augšdaļas. Otrajā posmā pēc katras ekstrakcijas kaudzi pārbūvē. Katra pārbūve ir ātrāka nekā sākotnējais būvniecības process, jo pārbūve tiek veikta no iepriekšējās konstrukcijas, kurā ir noņemts viens elements. Un līdz ar to heapsort sakārto pilnīgi nešķirotu sarakstu.

Šī raksta mērķis ir īsi izskaidrot kaudzi un pēc tam izveidot tā laika sarežģītību (skatiet laika sarežģītības nozīmi tālāk). Beigās kodēšana tiek veikta C++ valodā.

Minimālā kaudze

Kaudze var būt minimālā vai maksimālā kaudze. Maksimālais kaudze ir tāds, kurā pirmais elements ir augstākais elements, un viss koks vai atbilstošais saraksts ir daļēji sakārtots dilstošā secībā. Minimālais kaudze ir tāds, kurā pirmais elements ir vismazākais elements, un viss saraksts ir daļēji sakārtots augošā secībā. Šajā rakstā ir apskatīta tikai minimālā kaudze. Piezīme: kaudzes tēmā elementu sauc arī par mezglu.

Kaudzīte ir pilnīgs binārs koks. Bināro koku var izteikt kā masīvu (sarakstu); lasīt no augšas uz leju un no kreisās uz labo pusi. Minimālās kaudzes kaudzes īpašība ir tāda, ka vecākais mezgls ir mazāks vai vienāds ar katru no tā diviem atvasinātajiem. Nesakārtota saraksta piemērs ir:

Šīs tabulas pirmajā rindā ir masīva elementi. Otrajā rindā ir nulles indeksi. Šo elementu sarakstu var izteikt kā koku. Nulles elementi ir pievienoti, lai izveidotu pilnu bināro koku. Stingri sakot, nulles elementi neietilpst sarakstā (kokā). Šim sarakstam nav secības, tāpēc tas vēl nav kaudze. Tas kļūs par kaudzi, kad tas būs daļēji sakārtots atbilstoši kaudzes īpašumam.

Attiecības starp mezgliem un indeksiem

Atcerieties, ka kaudze ir pilnīgs binārs koks, pirms tam ir kaudzes konfigurācija (kaudzes rekvizīts). Iepriekšējais saraksts vēl nav kaudze, jo elementi nepakļaujas kaudzes īpašībai. Tas kļūst par kaudzi pēc elementu pārkārtošanas daļējā secībā atbilstoši min-heap īpašībai. Daļēju secību var uzskatīt par daļēju kārtošanu (lai gan vārds “kārtot” nozīmē pilnīgu kārtošanu).

Neatkarīgi no tā, vai binārais koks ir kaudze vai nē, katram vecākam ir divi bērni, izņemot lapas (pēdējos) mezglus. Starp katru vecāku un tā bērniem pastāv matemātiskas attiecības starp indeksiem. Tas ir šādi: Ja vecāks atrodas indeksā i, tad kreisais bērns atrodas indeksā:

un pareizais bērns ir rādītājā:

Tas ir paredzēts nulles indeksēšanai. Tātad vecākam ar indeksu 0 kreisais bērns ir indeksā 2 × 0 + 1 = 1, bet labais bērns ir 2 × 0 + 2 = 2. Vecākam ar indeksu 1 kreisais bērns ir ar indeksu 2×1+1=3 un labais bērns ar indeksu 2×1+2=4; un tā tālāk.

Pēc minimālās kaudzes rekvizīta vecākais, kas atrodas i, ir mazāks vai vienāds ar kreiso atvasi 2i+1 un mazāks vai vienāds ar labo bērnu pie 2i+2.

Kaudze

Kaudzēt nozīmē veidot kaudzi. Tas nozīmē saraksta (vai atbilstošā koka) elementu pārkārtošanu tā, lai tie atbilstu kaudzes īpašībai. Kaudzēšanas procesa beigās saraksts vai koks ir kaudze.

Ja iepriekšējais nešķirotais saraksts ir izveidots ar kaudzi, tas kļūs par:

Piezīme: sarakstā ir 12 elementi, nevis 15. Otrajā rindā ir indeksi. Kaudzes veidošanas procesā elementi bija jāpārbauda un daži no tiem jāmaina.

Ievērojiet, ka mazākais un pirmais elements ir 3. Pārējie elementi seko augošā, bet viļņveidīgā veidā. Ja kreisais un labais atvases pozīcijās 2i+1 un 2i+2 ir lielākas vai vienādas ar vecāku pozīcijā i, tad šī ir minimālā kaudze. Tā nav pilna pasūtīšana vai šķirošana. Šī ir daļēja pasūtīšana atbilstoši kaudzes īpašumam. No šejienes sākas nākamais kaudzes šķirošanas posms.

Palieliniet laika sarežģītību

Laika sarežģītība ir kāda koda relatīvais darbības laiks. To var uzskatīt par galveno darbību skaitu, kas jāpabeidz šim kodam. Ir dažādi kaudzes veidošanas algoritmi. Visefektīvākais un ātrākais nepārtraukti sadala sarakstu ar diviem, pārbaudot elementus no apakšas un pēc tam veicot elementu apmaiņu. Ļaujiet N ir praktisko elementu skaits sarakstā. Izmantojot šo algoritmu, maksimālais galveno operāciju (maiņu) skaits ir N. Kaudzes veidošanas laika sarežģītība iepriekš tika norādīta kā:

Kur n ir N un ir maksimālais iespējamais galveno darbību skaits. Šo apzīmējumu sauc par Big-O apzīmējumu. Tas sākas ar O ar lielajiem burtiem, kam seko iekavas. Iekavās ir izteiksme iespējami lielākajam darbību skaitam.

Atcerieties: saskaitīšana var kļūt par reizināšanu, ja viena un tā pati pievienojamā lieta atkārtojas.

Heapsort ilustrācija

Iepriekšējais nešķirotais saraksts tiks izmantots, lai ilustrētu kaudzes šķirošanu. Dotais saraksts ir:

No saraksta iegūtā minimālā kaudze ir:

Pirmais kaudzes kārtošanas posms ir saražotās kaudzes ražošana. Šis ir daļēji sakārtots saraksts. Tas nav sakārtots (pilnīgi sakārtots) saraksts.

Otrajā posmā tiek noņemts vismazākais elements, kas ir pirmais elements, no kaudzes, atlikušās kaudzes atkārtota uzkrāšana un vismazāko elementu noņemšana rezultātos. Mazākais elements vienmēr ir pirmais elements atkārtoti izveidotajā kaudzē. Elementi netiek noņemti un izmesti. Tos var nosūtīt uz citu masīvu tādā secībā, kādā tie ir noņemti.

Galu galā jaunajā masīvā visi elementi būtu sakārtoti (pilnībā), augošā secībā; un vairs tikai daļēji pasūtīts.

Otrajā posmā pirmā lieta, kas jādara, ir noņemt 3 un ievietot to jaunajā masīvā. Rezultāti ir:

un

Atlikušie elementi ir jāapkopo, pirms tiek iegūts pirmais elements. Atlikušo elementu kaudze var kļūt:

Izvelkot 5 un pievienojot jaunajam sarakstam (masīvam), tiek iegūti rezultāti:

un

Atlikušo komplektu papildināšana dotu:

Izvelkot 6 un pievienojot jaunajam sarakstam (masīvam), tiek iegūti rezultāti:

un

Atlikušo komplektu papildināšana dotu:

Izvelkot 7 un pievienojot to jaunajam sarakstam, tiek iegūti rezultāti:

un

Atlikušo komplektu papildināšana dod:

Izvelkot 9 un pievienojot jaunajam sarakstam, tiek iegūti rezultāti:

un

Atlikušo komplektu papildināšana dod:

Izvelkot 11 un pievienojot to jaunajam sarakstam, tiek iegūti rezultāti:

un

Atlikušo komplektu papildināšana dotu:

Izvelkot 14 un pievienojot to jaunajam sarakstam, tiek iegūti rezultāti:

un

Atlikušo komplektu papildināšana dotu:

Izvelkot 15 un pievienojot to jaunajam sarakstam, tiek iegūti rezultāti:

un

Atlikušo komplektu papildināšana dotu:

Izvelkot 17 un pievienojot to jaunajam sarakstam, tiek iegūti rezultāti:

un

Atlikušo komplektu papildināšana dotu:

Izvelkot 19 un pievienojot to jaunajam sarakstam, tiek iegūti rezultāti:

un

Atlikušo komplektu papildināšana dod:

Izvelkot 22 un pievienojot to jaunajam sarakstam, tiek iegūti rezultāti:

un

Atlikušo komplektu papildināšana dod:

Izvelkot 24 un pievienojot to jaunajam sarakstam, tiek iegūti rezultāti:

un

Kaudzes masīvs tagad ir tukšs. Visi elementi, kas tam bija sākumā, tagad atrodas jaunajā masīvā (sarakstā) un sakārtoti.

Heapsort algoritms

Lai gan lasītājs, iespējams, ir lasījis mācību grāmatās, ka kaudzes šķirošana sastāv no diviem posmiem, kaudzes šķirošanu joprojām var uzskatīt par sastāvošu no viena posma, kas iteratīvi samazina doto masīvu. Tādējādi kārtošanas algoritms ar kaudzes šķirošanu ir šāds:

• Palieliniet nešķiroto sarakstu.
• Izvelciet pirmo kaudzes elementu un ievietojiet to kā jaunā saraksta pirmo elementu.
• Sakārtojiet atlikušo sarakstu.
• Izvelciet jaunā kaudzes pirmo elementu un ievietojiet to kā nākamo jaunā saraksta elementu.
• Atkārtojiet iepriekšējās darbības secībā, līdz kaudzes saraksts ir tukšs. Beigās jaunais saraksts tiek sakārtots.

Pareiza kaudzes šķirošanas laika sarežģītība

Viena posma pieeja tiek izmantota, lai noteiktu kaudzes šķirošanas laika sarežģītību. Pieņemsim, ka ir jākārto 8 nešķiroti elementi.

Iespējamais maksimālais operāciju skaits ir:

Vidējais šo darbību skaits ir:

Ievērojiet, ka pēdējās četras kaudzes iepriekšējā attēlā nemainījās, kad tika noņemts pirmais elements. Dažas no iepriekšējām kaudzēm arī nemainījās, kad tika noņemts pirmais elements. Tādējādi labāks vidējais galveno operāciju (maiņu) skaits ir 3, nevis 4,5. Tātad labāks kopējais vidējais galveno operāciju skaits ir:

kopš žurnāla _divi 8 = 3.

Kopumā kaudzes šķirošanas gadījuma vidējā sarežģītība ir:

Ja punkts nozīmē reizināšanu un n ir N, kopējais elementu skaits sarakstā (vai nu sarakstā).

Ņemiet vērā, ka pirmā elementa izvilkšanas darbība ir ignorēta. Runājot par laika sarežģītību, tiek ignorētas darbības, kas aizņem salīdzinoši īsu laiku.

Kodēšana C++ valodā

C++ algoritmu bibliotēkā ir funkcija make_heap(). Sintakse ir:

Kā pirmo argumentu tiek izmantots iterators, kas norāda uz vektora pirmo elementu, un pēc tam kā pēdējais arguments ir iterators, kas norāda tieši aiz vektora beigām. Iepriekšējam nešķirotajam sarakstam sintakse tiks izmantota šādi, lai iegūtu minimālo kaudzi:

Šis kods maina vektora saturu minimālā kaudzes konfigurācijā. Turpmākajos C++ vektoros divu masīvu vietā tiks izmantoti divi vektori.

Lai kopētu un atgrieztu vektora pirmo elementu, izmantojiet vektora sintaksi:

Lai noņemtu pirmo vektora elementu un izmestu to, izmantojiet vektora sintaksi:

Lai pievienotu elementu vektora aizmugurē (nākamais elements), izmantojiet vektora sintaksi:

Programmas sākums ir:

Ir iekļauts algoritms un vektoru bibliotēkas. Nākamā programmā ir funkcija heapsort (), kas ir:

Tā ir rekursīva funkcija. Tas izmanto C++ algoritmu bibliotēkas funkciju make_heap(). Otrais koda segments funkcijas definīcijā izņem pirmo elementu no vecā vektora pēc kaudzes veidošanas un pievieno kā nākamo elementu jaunajam vektoram. Ņemiet vērā, ka funkcijas definīcijā vektora parametri ir atsauces, savukārt funkcija tiek izsaukta ar identifikatoriem (nosaukumiem).

Tam piemērota C++ galvenā funkcija ir:

Izvade ir:

sakārtots (pilnībā).

Secinājums

Rakstā detalizēti tika aplūkots Heap Sort, kas pazīstams kā Heapsort, kā šķirošanas algoritma būtība un funkcija. Heapify laika sarežģītība, Heapsort ilustrācija un Heapsort kā algoritms tika apskatīti un atbalstīti ar piemēriem. Vidējā laika sarežģītība labi uzrakstītai kaudzes šķirošanas programmai ir O(nlog(n))