Heapsort časová zložitosť

Halda sa označuje ako „čiastočne usporiadaná“ a nie „čiastočne vytriedená“. Slovo „triediť“ znamená úplné zoradenie (kompletné zoradenie). Hromada nie je čiastočne usporiadaná svojvoľne. Halda je čiastočne usporiadaná podľa kritéria (vzoru), ako je uvedené nižšie.

Heapsort teda pozostáva z dvoch etáp: zostavenie haldy a extrakcia usporiadaného prvku z hornej časti haldy. V druhej etape sa po každej ťažbe halda znovu postaví. Každá prestavba je rýchlejšia ako pôvodný stavebný proces, pretože prestavba sa vykonáva z predchádzajúcej stavby, kde bol odstránený jeden prvok. A s tým, heapsort triedi úplne netriedený zoznam.

Cieľom tohto článku je stručne vysvetliť heapsort a následne vytvoriť jeho časovú zložitosť (pozri význam časovej zložitosti nižšie). Ku koncu sa kódovanie vykonáva v C++.

Minimálna halda

Halda môže byť minimálna alebo maximálna halda. Maximálna halda je taká, kde prvý prvok je najvyšší prvok a celý strom alebo zodpovedajúci zoznam je čiastočne zoradený v zostupnom poradí. Minimálna halda je taká, kde prvý prvok predstavuje najmenší prvok a celý zoznam je čiastočne usporiadaný vo vzostupnom poradí. V tomto článku sa berie do úvahy len minimálna hromada. Poznámka: v téme halda sa prvok nazýva aj uzol.

Halda je úplný binárny strom. Binárny strom môže byť vyjadrený ako pole (zoznam); čítať zhora nadol a zľava doprava. Vlastnosť haldy pre mini-hromadu je, že nadradený uzol je menší alebo rovný každému z jeho dvoch potomkov. Príkladom neusporiadaného zoznamu je:

Prvý riadok tejto tabuľky sú prvky poľa. V druhom riadku sú indexy založené na nule. Tento zoznam prvkov možno vyjadriť ako strom. Boli pridané nulové prvky, aby sa vytvoril úplný binárny strom. Presne povedané, nulové prvky nie sú súčasťou zoznamu (stromu). Tento zoznam nemá poradie, takže to ešte nie je hromada. Stane sa haldou, keď bude mať čiastočné usporiadanie podľa vlastnosti haldy.

Vzťah medzi uzlami a indexmi

Pamätajte si, že halda je úplný binárny strom predtým, ako budete mať konfiguráciu haldy (vlastnosť haldy). Predchádzajúci zoznam ešte nie je halda, pretože prvky sa neriadia vlastnosťou halda. Stane sa haldou po preusporiadaní prvkov do čiastočného poradia podľa vlastnosti min-heap. Čiastočné zoradenie možno považovať za čiastočné zoradenie (hoci slovo „zoradiť“ znamená úplné zoradenie).

Či už je binárny strom hromadou alebo nie, každý rodič má dve deti, okrem listových (posledných) uzlov. Medzi indexmi medzi každým rodičom a jeho deťmi existuje matematický vzťah. Je to nasledovné: Ak je rodič na indexe i, potom ľavý potomok je na indexe:

a správne dieťa je na indexe:

Toto je pre indexovanie založené na nule. A tak rodič na indexe 0 má svojho ľavého potomka na indexe 2×0+1=1 a jeho pravého potomka na 2×0+2=2. Rodič na indexe 1 má svojho ľavého potomka na indexe 2×1+1=3 a pravého potomka na indexe 2×1+2=4; a tak ďalej.

Podľa vlastnosti min-heap je rodič v i je menší alebo rovný ľavému potomkovi v 2i+1 a menší alebo rovný pravému potomkovi v 2i+2.

Hromada

Hromadenie znamená budovanie hromady. Znamená to preusporiadať prvky zoznamu (alebo zodpovedajúceho stromu) tak, aby vyhovovali vlastnosti haldy. Na konci procesu hromadenia je zoznam alebo strom hromada.

Ak je predchádzajúci nezoradený zoznam nahromadený, stane sa:

Poznámka: v zozname je 12 prvkov a nie 15. V druhom riadku sú indexy. V procese budovania haldy bolo potrebné skontrolovať prvky a niektoré vymeniť.

Všimnite si, že najmenší a prvý prvok je 3. Ostatné prvky nasledujú vzostupne, ale zvlnene. Ak sú ľavé a pravé podriadené položky na pozíciách 2i+1 a 2i+2 väčšie alebo rovnaké ako rodič na i, potom ide o minimálnu hromadu. Toto nie je úplné zoradenie alebo triedenie. Toto je čiastočné zoradenie podľa vlastnosti haldy. Odtiaľ začína ďalšia fáza triedenia haldy.

Heapify časová zložitosť

Časová zložitosť je relatívna doba chodu nejakého kódu. Môže sa považovať za počet hlavných operácií, ktoré má tento kód dokončiť. Existujú rôzne algoritmy na vytváranie haldy. Najefektívnejšie a najrýchlejšie priebežne delia zoznam dvomi, kontrolujú prvky zdola a potom vymieňajú prvky. Nech N je počet praktických prvkov v zozname. S týmto algoritmom je maximálny počet hlavných operácií (swapovanie) N. Časová zložitosť heapifikácia bola predtým daná ako:

Kde n je N a je maximálny možný počet hlavných operácií. Tento zápis sa nazýva Big-O zápis. Začína sa písmenom O veľkým písmenom, za ktorým nasledujú zátvorky. V zátvorkách je výraz pre najvyšší možný počet operácií.

Pamätajte: sčítanie sa môže stať násobením, ak sa stále opakuje to isté, čo sa pridáva.

Heapsort ilustrácie

Predchádzajúci neutriedený zoznam sa použije na ilustráciu zoradenia. Uvedený zoznam je:

Minimálna hromada vytvorená zo zoznamu je:

Prvou fázou pri triedení haldy je výroba haldy, ktorá bola vyrobená. Toto je čiastočne usporiadaný zoznam. Nie je to zoradený (úplne zoradený) zoznam.

Druhá fáza pozostáva z odstránenia najmenšieho prvku, ktorý je prvým prvkom, z haldy, opätovného nahromadenia zostávajúcej haldy a odstránenia najmenšieho počtu prvkov vo výsledkoch. Najmenší prvok je vždy prvým prvkom v znovu nahromadenej halde. Prvky sa neodstraňujú a nevyhadzujú. Môžu byť odoslané do iného poľa v poradí, v akom boli odstránené.

Nakoniec by nové pole malo všetky prvky zoradené (úplne) vo vzostupnom poradí; a už nie len čiastočne objednané.

V druhej fáze je potrebné najskôr odstrániť 3 a umiestniť ich do nového poľa. Výsledky sú:

a

Zostávajúce prvky sa musia nahromadiť pred extrahovaním prvého prvku. Hromada zostávajúcich prvkov sa môže stať:

Extrahovaním 5 a pridaním do nového zoznamu (pola) získate výsledky:

a

Nahromadenie zostávajúcej sady by poskytlo:

Extrahovaním 6 a pridaním do nového zoznamu (pola) získate výsledky:

a

Nahromadenie zostávajúcej sady by poskytlo:

Extrahovaním 7 a jeho pridaním do nového zoznamu získate výsledky:

a

Nahromadením zostávajúcej sady získate:

Extrahovaním 9 a pridaním do nového zoznamu získate výsledky:

a

Nahromadením zostávajúcej sady získate:

Extrahovaním 11 a jej pridaním do nového zoznamu získate výsledky:

a

Nahromadenie zostávajúcej sady by poskytlo:

Extrahovaním 14 a jeho pridaním do nového zoznamu získate výsledky:

a

Nahromadenie zostávajúcej sady by poskytlo:

Extrahovaním 15 a jeho pridaním do nového zoznamu získate výsledky:

a

Nahromadenie zostávajúcej sady by poskytlo:

Extrahovaním 17 a jeho pridaním do nového zoznamu získate výsledky:

a

Nahromadenie zostávajúcej sady by poskytlo:

Extrahovaním 19 a jej pridaním do nového zoznamu získate výsledky:

a

Nahromadením zostávajúcej sady získate:

Extrahovaním 22 a jeho pridaním do nového zoznamu získate výsledky:

a

Nahromadením zostávajúcej sady získate:

Extrahovaním 24 a jeho pridaním do nového zoznamu získate výsledky:

a

Pole haldy je teraz prázdne. Všetky prvky, ktoré mal na začiatku, sú teraz v novom poli (zozname) a sú zoradené.

Heapsort algoritmus

Aj keď sa čitateľ mohol v učebniciach dočítať, že heapsort pozostáva z dvoch etáp, heapsort môže byť stále vnímaný ako pozostávajúci z jednej fázy, ktorá sa iteratívne zmenšuje z daného poľa. Algoritmus triedenia pomocou heapsortu je teda nasledujúci:

• Rozšírte netriedený zoznam.
• Extrahujte prvý prvok haldy a vložte ho ako prvý prvok nového zoznamu.
• Rozšírte zostávajúci zoznam.
• Extrahujte prvý prvok novej haldy a vložte ho ako ďalší prvok nového zoznamu.
• Opakujte predchádzajúce kroky v poradí, kým zoznam haldy nebude prázdny. Nakoniec je nový zoznam zoradený.

Správna časová zložitosť Heapsort

Jednostupňový prístup sa používa na určenie časovej zložitosti pre heapsort. Predpokladajme, že existuje 8 nezoradených prvkov na triedenie.

Maximálny možný počet operácií je:

Priemer týchto počtov operácií je:

Všimnite si, že posledné štyri kôpky na predchádzajúcej ilustrácii sa po odstránení prvého prvku nezmenili. Niektoré z predchádzajúcich kôp sa tiež nezmenili, keď bol odstránený prvý prvok. S tým je lepší priemerný počet hlavných operácií (swapov) 3 a nie 4,5. Takže lepší celkový priemerný počet hlavných operácií je:

od log _dva 8 = 3.

Vo všeobecnosti je priemerná časová zložitosť prípadu pre heapsort:

Kde bodka znamená násobenie a n je N, celkový počet prvkov v zozname (oboch zoznamoch).

Všimnite si, že operácia extrakcie prvého prvku bola ignorovaná. Pri téme časovej zložitosti sa ignorujú operácie, ktoré trvajú relatívne krátky čas.

Kódovanie v C++

V knižnici algoritmov C++ existuje funkcia make_heap(). Syntax je:

Ako svoj prvý argument berie iterátor ukazujúci na prvý prvok vektora a potom ako posledný argument iterátor ukazujúci tesne za koniec vektora. Pre predchádzajúci neutriedený zoznam by sa na získanie minimálnej haldy použila syntax nasledovne:

Tento kód zmení vektorový obsah na minimálnu konfiguráciu haldy. V nasledujúcich vektoroch C++ sa namiesto dvoch polí použijú dva vektory.

Ak chcete skopírovať a vrátiť prvý prvok vektora, použite syntax vektora:

Ak chcete odstrániť prvý prvok vektora a zahodiť ho, použite syntax vektora:

Ak chcete pridať prvok na zadnú stranu vektora (ďalší prvok), použite syntax vektora:

Začiatok programu je:

Obsahuje algoritmus a vektorové knižnice. Ďalej v programe je funkcia heapsort(), čo je:

Ide o rekurzívnu funkciu. Používa funkciu make_heap() knižnice algoritmov C++. Druhý segment kódu v definícii funkcie extrahuje prvý prvok zo starého vektora po vytvorení haldy a pridá ho ako ďalší prvok pre nový vektor. Všimnite si, že v definícii funkcie sú parametre vektora referencie, zatiaľ čo funkcia sa volá s identifikátormi (názvami).

Na to je vhodná hlavná funkcia C++:

Výstupom je:

triedené (úplne).

Záver

Článok podrobne rozoberá povahu a funkciu Heap Sort bežne známeho ako Heapsort ako triediaci algoritmus. Heapify Time Complexity, Heapsort ilustrácie a Heapsort ako algoritmus boli pokryté a podporené príkladmi. Priemerná časová zložitosť dobre napísaného heapsortového programu je O(nlog(n))