Heapsort Časová složitost

Hromada se označuje jako „částečně uspořádaná“ a nikoli „částečně roztříděná“. Slovo „sort“ znamená kompletní řazení (kompletní řazení). Hromada není částečně uspořádána libovolně. Halda je částečně uspořádána podle kritéria (vzoru), jak je znázorněno níže.

Heapsort se tedy skládá ze dvou fází: sestavení hromady a extrahování uspořádaného prvku z horní části hromady. Ve druhé fázi se po každé extrakci halda znovu postaví. Každá přestavba je rychlejší než původní stavební proces, protože přestavba se provádí z předchozí stavby, kde byl odstraněn jeden prvek. A s tím heapsort třídí zcela netříděný seznam.

Cílem tohoto článku je stručně vysvětlit heapsort a následně vytvořit jeho časovou složitost (viz význam časové složitosti níže). Ke konci se kódování provádí v C++.

Minimální halda

Halda může být minimální halda nebo maximální halda. Maximální halda je taková, kde první prvek je nejvyšší prvek a celý strom nebo odpovídající seznam je částečně uspořádán v sestupném pořadí. Min-hromada je taková, kde první prvek je nejmenší prvek a celý seznam je částečně seřazen vzestupně. V tomto článku je uvažována pouze minimální hromada. Poznámka: v tématu haldy se prvek nazývá také uzel.

Halda je úplný binární strom. Binární strom může být vyjádřen jako pole (seznam); čtěte shora dolů a zleva doprava. Vlastností haldy pro min-hromadu je, že nadřazený uzel je menší nebo roven každému z jeho dvou potomků. Příkladem neuspořádaného seznamu je:

První řádek této tabulky jsou prvky pole. Ve druhém řádku jsou indexy založené na nule. Tento seznam prvků lze vyjádřit jako strom. Nulové prvky byly přidány, aby se vytvořil úplný binární strom. Přísně vzato, prvky null nejsou součástí seznamu (stromu). Tento seznam nemá pořadí, takže to ještě není hromada. Stane se haldou, když má částečné uspořádání podle vlastnosti haldy.

Vztah mezi uzly a indexy

Pamatujte, že halda je úplný binární strom předtím, než budete mít konfiguraci haldy (vlastnost haldy). Předchozí seznam ještě není halda, protože prvky se neřídí vlastností haldy. Stane se haldou po přeskupení prvků do částečného pořadí podle vlastnosti min-heap. Částečné pořadí může být chápáno jako částečné řazení (ačkoli slovo „sort“ znamená úplné uspořádání).

Ať už je binární strom hromada nebo ne, každý rodič má dvě potomky, kromě listových (posledních) uzlů. Mezi indexy mezi každým rodičem a jeho dětmi existuje matematický vztah. Je to takto: Pokud je rodič na indexu i, pak je levý potomek na indexu:

a správné dítě je na indexu:

Toto je pro indexování založené na nule. A tak rodič na indexu 0 má svého levého potomka na indexu 2×0+1=1 a jeho pravého potomka na 2×0+2=2. Rodič na indexu 1 má svého levého potomka na indexu 2×1+1=3 a pravého potomka na indexu 2×1+2=4; a tak dále.

Podle vlastnosti min-heap je rodič na i menší nebo roven levému potomkovi v 2i+1 a menší nebo roven pravému potomkovi v 2i+2.

Halda

Hromadit znamená stavět hromadu. Znamená to přeskupit prvky seznamu (nebo odpovídajícího stromu) tak, aby vyhovovaly vlastnosti haldy. Na konci procesu hromadění je seznam nebo strom hromada.

Pokud je předchozí neseřazený seznam nahromaděný, stane se:

Poznámka: v seznamu je 12 prvků, nikoli 15. Ve druhém řádku jsou indexy. V procesu vytváření haldy bylo nutné prvky zkontrolovat a některé vyměnit.

Všimněte si, že nejmenší a první prvek je 3. Zbytek prvků následuje vzestupně, ale zvlněně. Pokud je levý a pravý potomek na pozicích 2i+1 a 2i+2 větší než nebo stejný jako rodič na i, pak je to min-hromada. Toto není úplné řazení nebo řazení. Toto je částečné řazení podle vlastnosti haldy. Odtud začíná další fáze třídění haldy.

Heapify Time Complexity

Časová složitost je relativní doba běhu nějakého kódu. Může být viděn jako počet hlavních operací, které má tento kód dokončit. Existují různé algoritmy pro vytváření haldy. Nejúčinnější a nejrychlejší průběžně rozdělují seznam po dvou, kontrolují prvky odspodu a poté provádějí nějaké prohození prvků. Nechť N je počet praktických prvků v seznamu. S tímto algoritmem je maximální počet hlavních operací (swapování) N. Časová složitost heapifikace byla dříve dána jako:

Kde n je N a je maximální možný počet hlavních operací. Tato notace se nazývá Big-O notace. Začíná velkým písmenem O, za nímž následují závorky. Uvnitř závorek je výraz pro možný nejvyšší počet operací.

Pamatujte: sčítání se může stát násobením, pokud se stále opakuje totéž, co se přidává.

Heapsort ilustrace

Předchozí neseřazený seznam bude použit pro ilustraci heapsortu. Uvedený seznam je:

Min-hromada vytvořená ze seznamu je:

První fází v heapsort je vytvoření hromady, která byla vyrobena. Toto je částečně uspořádaný seznam. Nejedná se o seřazený (zcela seřazený) seznam.

Druhá fáze spočívá v odstranění nejmenšího prvku, což je první prvek, z hromady, opětovném nahromadění zbývající hromady a odstranění nejmenšího počtu prvků ve výsledcích. Nejmenší prvek je vždy prvním prvkem v re-heapifyied haldě. Prvky se neodstraňují a nevyhazují. Mohou být odeslány do jiného pole v pořadí, v jakém byly odebrány.

Nakonec by nové pole mělo všechny prvky seřazené (zcela), ve vzestupném pořadí; a už ne jen částečně objednané.

Ve druhé fázi je první věcí, kterou musíte udělat, odstranit 3 a umístit je do nového pole. Výsledky jsou:

a

Zbývající prvky musí být nahromaděny před extrakcí prvního prvku. Hromada zbývajících prvků se může stát:

Extrahováním 5 a přidáním do nového seznamu (pole) získáte výsledky:

a

Nahromadění zbývající sady by poskytlo:

Extrahováním 6 a přidáním do nového seznamu (pole) získáte výsledky:

a

Nahromadění zbývající sady by poskytlo:

Rozbalením 7 a jeho přidáním do nového seznamu získáte výsledky:

a

Nahromadění zbývající sady dává:

Rozbalením 9 a přidáním do nového seznamu získáte výsledky:

a

Nahromadění zbývající sady dává:

Rozbalením 11 a jeho přidáním do nového seznamu získáte výsledky:

a

Nahromadění zbývající sady by poskytlo:

Extrahováním 14 a jeho přidáním do nového seznamu získáte výsledky:

a

Nahromadění zbývající sady by poskytlo:

Extrahováním 15 a jeho přidáním do nového seznamu získáte výsledky:

a

Nahromadění zbývající sady by poskytlo:

Extrahováním 17 a jeho přidáním do nového seznamu získáte výsledky:

a

Nahromadění zbývající sady by poskytlo:

Extrahováním 19 a jeho přidáním do nového seznamu získáte výsledky:

a

Nahromadění zbývající sady dává:

Extrahováním 22 a jeho přidáním do nového seznamu získáte výsledky:

a

Nahromadění zbývající sady dává:

Extrahováním 24 a jeho přidáním do nového seznamu získáte výsledky:

a

Pole haldy je nyní prázdné. Všechny prvky, které měl na začátku, jsou nyní v novém poli (seznamu) a jsou seřazeny.

Algoritmus Heapsort

Ačkoli se čtenář v učebnicích mohl dočíst, že heapsort se skládá ze dvou fází, heapsort může být stále považován za sestávající z jedné fáze, která se iterativně zmenšuje z daného pole. S tím je algoritmus pro řazení pomocí heapsort následující:

• Rozšiřte netříděný seznam.
• Extrahujte první prvek haldy a vložte jej jako první prvek nového seznamu.
• Rozšiřte zbývající seznam.
• Extrahujte první prvek nové haldy a vložte jej jako další prvek nového seznamu.
• Opakujte předchozí kroky v pořadí, dokud není seznam haldy prázdný. Nakonec se nový seznam seřadí.

Heapsort Časová složitost Správná

Jednostupňový přístup se používá k určení časové složitosti pro heapsort. Předpokládejme, že existuje 8 neseřazených prvků, které mají být seřazeny.

Maximální možný počet operací je:

Průměr těchto počtů operací je:

Všimněte si, že poslední čtyři hromady na předchozím obrázku se nezměnily, když byl odstraněn první prvek. Některé z předchozích hald se také nezměnily, když byl odstraněn první prvek. S tím je lepší průměrný počet hlavních operací (swappingů) 3 a ne 4,5. Takže lepší celkový průměrný počet hlavních operací je:

od log _dva 8 = 3.

Obecně je průměrná časová složitost pro heapsort:

Kde tečka znamená násobení an je N, celkový počet prvků v seznamu (v obou seznamech).

Všimněte si, že operace extrakce prvního prvku byla ignorována. U tématu časové složitosti jsou ignorovány operace, které trvají relativně krátkou dobu.

Kódování v C++

V knihovně algoritmů C++ existuje funkce make_heap(). Syntaxe je:

Jako svůj první argument bere iterátor ukazující na první prvek vektoru a jako poslední argument pak iterátor ukazující těsně za konec vektoru. Pro předchozí neseřazený seznam by se syntaxe použila následovně, aby se získala minimální hromada:

Tento kód změní vektorový obsah na konfiguraci minimální haldy. V následujících vektorech C++ budou místo dvou polí použity dva vektory.

Chcete-li zkopírovat a vrátit první prvek vektoru, použijte syntaxi vektoru:

Chcete-li odstranit první prvek vektoru a zahodit jej, použijte syntaxi vektoru:

Chcete-li přidat prvek na zadní stranu vektoru (další prvek), použijte syntaxi vektoru:

Začátek programu je:

Algoritmus a vektorové knihovny jsou zahrnuty. Další v programu je funkce heapsort(), což je:

Je to rekurzivní funkce. Používá funkci make_heap() knihovny algoritmů C++. Druhý segment kódu v definici funkce extrahuje první prvek ze starého vektoru po vytvoření haldy a přidá jej jako další prvek pro nový vektor. Všimněte si, že v definici funkce jsou parametry vektoru odkazy, zatímco funkce je volána s identifikátory (jmény).

Vhodná hlavní funkce C++ pro to je:

Výstup je:

seřazeno (zcela).

Závěr

Článek podrobně pojednává o povaze a funkci Heap Sort běžně známého jako Heapsort jako třídícího algoritmu. Heapify Time Complexity, Heapsort ilustrace a Heapsort jako algoritmus byly pokryty a podpořeny příklady. Průměrná časová složitost dobře napsaného heapsortového programu je O(nlog(n))