Diskuze – Lekce 4 - Heapsort

Zpět

Upozorňujeme, že diskuze pod našimi online kurzy jsou nemoderované a primárně slouží k získávání zpětné vazby pro budoucí vylepšení kurzů. Pro studenty našich rekvalifikačních kurzů nabízíme možnost přímého kontaktu s lektory a studijním referentem pro osobní konzultace a podporu v rámci jejich studia. Toto je exkluzivní služba, která zajišťuje kvalitní a cílenou pomoc v případě jakýchkoli dotazů nebo projektů.

Komentáře

Martin Dráb

Tvůrce

Martin Dráb:21.7.2011 1:08

Já vím, že jsem hrozný šťoural a pořád otravuju rádoby chytrými řečmi, ale prostě mi to nedá. Mám několik poznámek.

U Heapsortu nemusíš uvádět pouze složitost v průměrném případě, protože on má O(n log n) i v případě nejhorším (to je právě výhoda oproti v průměrném případě rychlejšímu Quicksortu).

Při odůvodňování složitosti je také třeba nezapomenout na to, že před započetím samtoného třídění se musí halda postavit. To také ubírá nějaký čas. Přičemž tebou prezentovaný způsob stavění haldy má myslím složitost také O(n log n), což ale samozřejmě nemá vliv na asymptotickou složitost celého algoritmu (O(n log n)). Prostě se jedná o dvě fáze, každá provede O(n log n) kroků (porovnání).

Existuje ale ještě jiný způsob stavění haldy, který je rychlejší (O(n)). Je svým způsobem opačný k tomu tvému. Celé pole se myšlenkově převede do toho skoro vyváženého binárního stromu a následně se z něho staví halda.

Halda se ale staví odspodu. Tzn. postup je takovýto:

Prvky na nejhlubší hladině (je jich až n/2) nemají žádné potomky, tedy netřeba s nimi nic provádět.
Prvky na hladině o jedna výše (je jich kolem N/4) je třeba porovnat s jejich syny a případně vyměnit. Ale protože jsou vzdáleny pouze 1 od nejhlubší hladiny, s každým se tahle výměna provede nejvýše jednou.
S prvky na hladině ještě o jedna výše se provádí obdobná věc... přičemž se mohou "probublat" až do listů, tedy s každým z nich (je jich okolo n/8) max. dvě operace

A tak se jde dál a dál, až dojdeme na hladinu, kde leží kořen (s tím se provede max. log n operací).

Vyplývá z toho následující:

s n/2 prvky se neprovádí žádná operace
s n/4 prvky se provádí max. jedna výměna
s n/8 prvky se provádí max. 2 výměny

Když budeme chtít odhadnout počet výměn, zjistíme, že to je n/4 + 2n/8 + 3n/16 + .... = n/2 + n/4 + n/8 + ... = n, tedy výměn se provede max. O(n), takže haldu lze postavit v lineárním čase. Samozřejmě, celkovou složitost algoritmu to dramaticky (v řeči asymptotické složitosti) neovlivní, pořád to bude n(log n).

A konec rýpání, popis algoritmu je to podle mého názoru velmi podařený! Mít takovouhle algoritmovou encyklopedii na serveru není vůbec špatné...

Odpovědět

21.7.2011 1:08

2 + 2 = 5 for extremely large values of 2

David Hartinger

Vlastník

David Hartinger:21.7.2011 9:30

Ahoj,
předně děkuji za zájem

Složitost v průměrném případě - vím, chtěl jsem se o tom začít zmiňovat až v souvislosti s Quicksortem, který má dolní hranici O(n²). Pokud narážíš na tu tabulku, tak ta je všude stejná, vždy je tam jen průměrný případ, protože je nejdůležitější, případné odchylky budou zmíněné v textu.

O stavění haldy jsem se nezmiňoval záměrně, protože se dělá jen jednou a věděl jsem, že je O(n log n). Ale máš samozřejmě pravdu, kdyby byla O(n²), tak by to pokazilo složitost celého algoritmu. Informaci doplním, je potřeba.

Vím, že jde postavit jinak a ani mi tento způsob nepřijde nejlepší, ale z hlediska asymptotické složitosti to nevadí a nechtěl jsem zbytečně přebírat jiný způsob, když tento jsem se naučil ve škole a dobře ho znám (je i na těch videích, musel bych je přetočit). Nadšenci si mohou implementovat tvůj způsob

Ještě chci udělat alespoň jednu takovou algoritmovou aktualizaci, tak jsem zvědavý, jak mi to půjde

Odpovědět

21.7.2011 9:30

New kid back on the block with a R.I.P

prasopes

Neregistrovaný

prasopes:28.5.2013 21:51

Ahoj, moc díky za videa řadících algoritmů - super, pomohly mi. :-)

Odpovědět

28.5.2013 21:51

David Šafrata

Člen

David Šafrata:10.11.2015 13:11

Build heap má složitost O(n). Dá se to dokázat přes konvergující sumu, viz http://stackoverflow.com/…d-a-max-heap

Odpovědět

10.11.2015 13:11

Xškin Domine Pusiak

Člen

Xškin Domine Pusiak:29.6.2016 21:21

Dakujem za clanok a vysvetlenie velmi mi pomohli. Autorovi patri obrovska vdaka.

Odpovědět

29.6.2016 21:21

Jan Troják

Člen

Jan Troják:12.8.2017 17:17

Ahoj,
mám pocit, že tam je chyba:
původní:
########################################################
Na první prvek (kořen, 3) funkci up pouštět nebudeme, protože ten žádného otce nemá. Začneme tedy s prvkem 2, ten je menší než otec, necháme ho na místě. Další je prvek 5, ten je větší než otec (3), proto ho s otcem prohodíme a jsme již v kořeni, takže končíme. Prvek 1 je menší než 2, to je v pořádku. 9 je však větší než 2, proto je prohodíme. 9 je však stále větší než --------------------3--------------, prohodíme tedy znovu a 9 (maximum) se dostává do kořene. 4 je větší než 3, proto prohodíme. 4 je potom menší než 9, to je již v pořádku. Zhaldované pole a halda, kterou reprezentuje, vypadají následovně:
########################################################

oprava:
########################################################
Na první prvek (kořen, 3) funkci up pouštět nebudeme, protože ten žádného otce nemá. Začneme tedy s prvkem 2, ten je menší než otec, necháme ho na místě. Další je prvek 5, ten je větší než otec (3), proto ho s otcem prohodíme a jsme již v kořeni, takže končíme. Prvek 1 je menší než 2, to je v pořádku. 9 je však větší než 2, proto je prohodíme. 9 je však stále větší než -----------------5---------------, prohodíme tedy znovu a 9 (maximum) se dostává do kořene. 4 je větší než 3, proto prohodíme. 4 je potom menší než 9, to je již v pořádku. Zhaldované pole a halda, kterou reprezentuje, vypadají následovně:
########################################################

V kořenu je již 5 a ne 3 -> tu jsme prohodili právě s 5 na pozici 2 (index od 0)

Editováno 12.8.2017 17:19

Odpovědět

12.8.2017 17:17

karolko

Člen

karolko:28.3.2018 7:53

mam jednu otazku, ale je to skor k syntaxu v jave: v motede down napr. je v if-else vetve aj return statement, ked nic nie je treba urobit:

else
return;

Funkcia prirodezene konci aj tak. Je tam treba return statement dodat alebo je to jedno? zrejme to moze mat vyznam re uvolnovanie operacnej pamate, a teda moze to byt dobry code practice, ale neviem, preto sa pytam.

Odpovědět

28.3.2018 7:53

krepsy3

Tvůrce

krepsy3:22.8.2018 16:53

Ahoj, díky za článek. Chci upozornit na chybu (byť nepatrňoulinkou):

Jistě jste si všimli, že prvky v poli jsou prvky tak, jak jsou v haldě, seřazené shora dolů a zleva doprava.

Tato věta na mě působí tak, že se nejprve řadí (indexuje) shora dolů, pak zleva doprava.To by pro haldu

       9
   7       8
 5   4   0   3
2 1 2

Znamenalo následující pole

0 1 2 3 4 5 6 7 8 9
9 7 5 2 1 4 2 8 0 3

A nikoliv to které chceme, tedy zleva doprava a shora dolů

Editováno 22.8.2018 16:54

Odpovědět

22.8.2018 16:53

Programátor je stroj k převodu kávy na kód.

Peter Večera

Člen

Peter Večera:17.7.2019 15:37

Ahoj myslím že v tejto vete je chyba :
je to veta nad tretím obrázkom heapsortu, tretí odstavec od spodu.
je prohodíme. 9 je však stále větší než 3, prohodíme tedy znovu a 9 (maximum) se dostává do kořene.
Podľa mňa tam má byť na miesto 3 5-ka. Veta by mala byť :
je prohodíme. 9 je však stále větší než 5, prohodíme tedy znovu a 9 (maximum) se dostává do kořene.

Editováno 17.7.2019 15:38

Odpovědět

17.7.2019 15:37

Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 9 zpráv z 9.

Nejčastěji vyhledáváné

Diskuze – Lekce 4 - Heapsort