wz


HeapSort - Tajemství odhaleno :)

Ξ February 28th, 2007 | → | ∇ Uncategorized |

Před pár dny jsem se začal zabývat HeapSortem, protože je to neskutečně rychlý (jeden z nejrychlejších vůbec), paměťově nenáročný (nerekurzivní) třídící algoritmus. Ku příkladu pole, které má BubbleSort seřízené za 2 sekundy, má heapsort za 16 milisekund. Dlouho jsem nemohl přijít na to, jak funguje a štvalo mě to. Teď, když jsem sám ručně setřídil pomocí heapsortu 14timístné číslo (na gauči :)), jsem spokojen.

Základem HeapSortu je datová struktura nazývaná Heap. Heap je vlastně takový strom, jehož jedna větev má pouze dva potomky a potomci potomků mají také pouze dva potomky. Z číselné řady vytvoříte Heap tak, že vezmete první číslo - to bude rodič a přiřadíte mu dvě další po sobě jdoucí nepoužitá čísla jako potomky (nepoužitá zn. nepoužitá do heapu ani jako rodič ani jako potomek). Následně vezmete další číslo (jeden z potomků prvního rodiče) a přiřadíte mu další dva nepoužitá čísla jako potomky. Takto postupujte až do konce řady. Rodič může mít dva, jednoho nebo žádného potomka. Uvedu příklad Heapu:

Heap z řady 65873159 :
6
5    8
7 3  1 5
9

Doufám, že je vám nyní naprosto jasné jak uděláte Heap, neboť teď popíšu samotný HeapSort.

Postupujeme odzdola: Je-li jeden z potomků větší, než jeho rodič, dochází ke switchovací příležitosti a potomek se vymění s rodičem. To samé provedem s paralelními větvemi. Pokud již v nejnižší úrovni větví neexistuje žádná switchovací příležitost, uděláme to samé s další úrovní (pokaždé, když dojde k výměně ve vyšší úrovni, je pravděpodobné, že výměna způsobila výskyt switchovací příležitosti v levelu nižším. pakliže tato příležitost nastala, přerušíme operace s vyšší úrovní a switchujeme tu, ve které nastala příležitost. Jestliže v žádném z levelů již nejsou switchovací příležitosti, pokračujeme s vyššími levely). Výsledkem této operace bude základní Heap, který na vrcholu obsahuje nejvyšší číslo. Jestliže máme tento základní Heap, můžeme začít třídit. Označme si nejvyšší prvek Heapu jako hlavní prvek a očíslujme si prvky heapu posupně sériově přes řady zleva od jedničky. Hlavní prvek
prohodíme s prvkem, který má nejnižší číslo. Na prvku
s nejnižším
číslem bude nyní nejvyšší číslo z řady. Tento prvek zalockujeme, to znamená, že ho vyřadíme z heapu. Změnou hlavního prvku došlo v Heapu ke switchovací příležitosti na druhé úrovni. Postupně switchujeme prvky od nejvyšší úrovně k nejnižší (nejvyšší úroveň vždy obsahuje jediný prvek - hlavní prvkek). Jsou-li všechny switchovací příležitosti využity, switcheme hlavní prvek s nejnižším (tentokrát to bude druhý) a následně onen prvek zalockujeme. Takto postupujeme až na konec algoritmu, kdy jsou zalockovány všechny prvky. Prvky jsou nyní seřazeny od nejnižšího (hlavní) po nejvyšší (první).

Napsal jsem ukázku třídění menšího pole HeapSortem:

 

24 Responses to ' HeapSort - Tajemství odhaleno :) '

Subscribe to comments with RSS or TrackBack to ' HeapSort - Tajemství odhaleno :) '.


  1. on March 4th, 2007 at 11:43 pm

    Sorry, ale psát takovýhle články do blogu kterej čtou jenom tví spolužáky je mrhání časem. To už to raději postni třeba na programujte.com nebo udělej něco, aby to našel google. Tenhle článek nenajde ani když mu dám celej nadpis.

  2. michaelf.ms said,

    on March 5th, 2007 at 4:53 pm

    podíl spolužáků a lidí, kteří přišli z vyhledávačů je 50:50. nemůžeš ho najít proto, že ještě není indexovanej…


  3. on March 5th, 2007 at 5:49 pm

    Takže když něco google nenajde tak to znamená že to není zaindexovaný ? To jsem nevěděl :D Fakt nečekaný.

  4. admin majk f testuje antispam said,

    on March 18th, 2007 at 6:29 pm

    testuju

  5. Turambar said,

    on December 28th, 2007 at 12:01 am

    Heh Antonín Daněk - sorry musím se smát. Zrovna hledám nějaký rozumný vysvětlení o heapsortu - všude jen algoritmy - respektive zdrojáky různých jazyků. Mě je to fuk, chtěl jsem jen vědět, jak to funguje a zde je to zrovna popsaný pěkně :D. Takže zrovna tento blog nečte jeho spolužák :D.

  6. MrBobby said,

    on January 8th, 2008 at 6:59 am

    Souhlasim s Turambarem ;) Taky hledam vsude mozne a tady to vysvetlujes na urovni, kdy se to da docela pochopit

  7. michaelf.ms said,

    on January 8th, 2008 at 3:39 pm

    Paráda. Takový komenty potěší. Mám ještě někde zdrojáky různých sortů v C++/CLI, kdyby někdo třeba chtěl :) …

  8. Bachy said,

    on January 17th, 2008 at 7:30 pm

    Přesně tak. Učím se na Databáze a hledám nějaké pořádné vysvětlení Heap sortu, nikde nic. Tento odkaz mi google našel jako 4. nebo 5. v pořadí, takže Antonín Daněk ať si jde hasit žáhu na jiných stránkách. Chtěl bych vidět, jestli on je schopný takto shopně vysvětlit nějaký algoritmus. Tímto ještě děkuji autorovi tohoto blogu.

  9. tomas said,

    on May 12th, 2008 at 12:48 am

    Ucim se na statnice a do algoritmu potrebuju vzpomenou na tridici algoritmy. Je tu videt snaha o dobry popis, ale je to dost spatne prezentovane, kdyz popisuju nejaky algoritmus na stromu, je zadouci aby prezentovany strom mel tzv. bubliny srozumitelne pospojovane, bohuzel takto se v tom ztracim :( v obrazku mi neni jasne jak je sipkou odkaz na zakladni heap “rosada” 5 za 6 z jinych casti stromu nez otec(syn,dcera), pokud to teda dobre chapu, skoda, ne a ne to pochopit

  10. Dutohlav said,

    on May 14th, 2008 at 6:03 pm

    Ja si myslim, ze je to rozpitvane dostatecne. Hledala jsem taky nejake jednoduche nazorne vysvetleni. diky

  11. LLL said,

    on May 17th, 2008 at 9:56 pm

    Parada konecne sem to pochopila:)))

  12. michalrost said,

    on July 2nd, 2008 at 8:23 am

    moc nesouhlasim s predchozim prispevkem, protoze tenhle blog je a) paradni b) nectou ho jenom tvoji spoluzaci ;) ..jen tak dal

  13. michalrost said,

    on July 2nd, 2008 at 8:24 am

    aha sorry, jsem si nevsim ze nejnovejsi prispevek de na konec :o)) …takze oprava, moc nesouhlasim s prvnim prispevkem ;D

  14. nahodny_host said,

    on November 25th, 2008 at 11:23 pm

    ja som rada, ze som narazila na tento web. Konecne som nasla nieco, kde je vysvetleny princip a nie len nejaky suchy zdrojak, z ktoreho clovek nic nema :)
    p.s.: nie som spoluziackou dotycneho a ani ho vobec nepoznam, ale za tento prispevok mu dakujem :)

  15. Amok said,

    on June 1st, 2009 at 3:50 pm

    Dobreej članek, hezky vysvětleno :-)

  16. tm said,

    on June 16th, 2009 at 7:24 pm

    Jen malá poznámka… “Heapu” se česky běžně říká halda.

  17. Lendys said,

    on July 7th, 2009 at 10:47 am

    na rozdil od tomase si nemyslim, ze by to bylo spatne citelne (samozrejme, kdyz se nekdo s binarnim stromem uz setkal), ale cely ten popis neni uplne spravny. Heap (halda) rozhodne neni jiz ten prvni strom. Binarni strom musi splnovat par podminek, aby byl nazvan haldou. Nazvat heapem by se mohlo az to, co nazyvas “zakladni heap”. ale bohuzel ani to neni heap. Mela by se vymenit 4 s 5. Pro heap (maximalni) plati, ze pro kazdy uzel jsou vsichni jeho naslednici mensi nez ten uzel. Pak je koren (nejvyssi uzel) maximalni. Pro minimalni heap je nerovnost obracene.

  18. kuba said,

    on January 19th, 2010 at 9:51 pm

    fajn vysvětleni, aspon je tomu rozumnět narozdil od wikipedie :)

  19. arenaq said,

    on June 28th, 2010 at 7:44 am

    dokonce i po dvou letech sem využil tvého popisku na oživení tohoto algoritmu ke zkoušce, dík :-)

  20. Tono said,

    on January 10th, 2011 at 9:20 pm

    Diky, dakujem za vysvetlenie, taketo nieco som hladal a konecne nasiel.

  21. Robert said,

    on May 9th, 2011 at 7:00 pm

    Super. Díky moc za help. A kamarád Daněk trochu přestřelil. Já si vážím každého kdo něco napíše pro někoho koho nezná. Takže ještě jednou díky :)

  22. Robert said,

    on May 9th, 2011 at 7:04 pm

    Jo a ještě info a rada. Když vidím nahoře ty reklamy, tak předpokládám, že asi jde o free hosting ic.cz, že? Tak jestli můžu poradit, doporučuji http://www.endora.cz. Nejde o reklamu, já s nimi nic společného nemám. Ale na ic.cz jsem hostoval nějaký ten rok a teď jsem všechno hodil na endoru, protože: a, Reklamy jsou na konci stránky b, Endora fakt jede slušně. Nepadá jáko ic.cz. A o administraci atd. ani nemluvím :)

  23. JoyeJoeJoejr said,

    on June 4th, 2011 at 7:43 pm

    Super článek, díky. :)

  24. Honza said,

    on June 12th, 2011 at 4:18 pm

    “Antonín Daněk said,

    on March 4th, 2007 at 11:43 pm

    Sorry, ale psát takovýhle články do blogu kterej čtou jenom tví spolužáky je mrhání časem. To už to raději postni třeba na programujte.com nebo udělej něco, aby to našel google. Tenhle článek nenajde ani když mu dám celej nadpis.”

    Odpověď formou citace z filmu Občanský průkaz: “Polib nám prdel, Daňku” :-) Článek je supr.

Leave a reply



dejmito

Leviathan

    kdo je Leviathan

    Jsem student aktuálně čtvrtého ročníku střední průmyslové školy strojní a elektrotechnické v českých budějovicích

     


 


RSS Zdroj

    ::

    RSS 2.0 < ZDE

    Přidejte si můj zdroj do vaší RSS čtečky

     

Statistiky