Diskusia – Heapsort

Späť

Upozorňujeme, že diskusie pod našimi online kurzami sú nemoderované a primárne slúžia na získavanie spätnej väzby pre budúce vylepšenie kurzov. Pre študentov našich rekvalifikačných kurzov ponúkame možnosť priameho kontaktu s lektormi a študijným referentom pre osobné konzultácie a podporu v rámci ich štúdia. Toto je exkluzívna služba, ktorá zaisťuje kvalitnú a cielenú pomoc v prípade akýchkoľvek otázok alebo projektov.

Komentáre

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é...

Odpovedať

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

Odpovedať

21.7.2011 9:30

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

prasopes

Nevyplnené

prasopes:28.5.2013 21:51

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

Odpovedať

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

Odpovedať

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.

Odpovedať

29.6.2016 21:21

Jan Troják

Brigádník

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)

Editované 12.8.2017 17:19

Odpovedať

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.

Odpovedať

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ů

Editované 22.8.2018 16:54

Odpovedať

22.8.2018 16:53

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

Peter Večera

Brigádník

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.

Editované 17.7.2019 15:38

Odpovedať

17.7.2019 15:37

Robíme čo je v našich silách, aby bola tunajšia diskusia čo najkvalitnejšia. Preto do nej tiež môžu prispievať len registrovaní členovia. Pre zapojenie sa do diskusie sa zaloguj. Ak ešte nemáš účet, zaregistruj sa, je to zadarmo.

Zatiaľ nikto nevložil komentár - buď prvý!

Najčastejšie vyhľadávané

Diskusia – Heapsort