September discount week
Tento týden až 80% sleva na e-learning týkající se jazyka C
50 % bodů zdarma na online výuku díky naší Slevové akci!

Heapsort

Heapsort patří mezi chytré algoritmy, které jsou řádově rychlejší než ty doposud zmíněné. Staví na myšlenkách algoritmu Selection sort a je tedy založený na odtrhávání extrému (v tomto případě maxima), které vždy přesouvá na konec pole. Po začlenění všech maxim na konec máme jistě pole setříděné. Problém Selection sortu však byl právě ve hledání maxima nebo minima. V každém vnějším cyklu se celá nesetříděná část pole musela projet a každý prvek zkontrolovat, zda není náhodou hledaným maximem. V poli maximum rychleji asi nenalezneme.

Ale co kdyby existovala datová struktura, ve které bychom mohli prvky reprezentovat stejně, jako v poli, a zároveň jsme maximum nalezli v konstantním čase, bez jediného průchodu? Když se takto ptám, asi vám je již jasné, že struktura existovat bude. Nazývá se Halda (anglicky Heap, proto Heap sort neboli třídění haldou).

Halda je binárním stromem s následujícími vlastnostmi:

  • Všechna "patra" haldy až na poslední jsou plně obsazeny prvky (tedy každý vnitřní vrchol má právě 2 syny, strom je velmi vyvážený)
  • Poslední patro haldy je zaplněno zleva (může být i zaplněno celé)
  • Pro prvky v haldě platí tzv. speciální vlastnost haldy: oba synové jsou vždy menší nebo rovny otci.

Ze speciální vlastnosti haldy nutně vyplývá, že v kořeni bude vždy uloženo maximum, což se nám velmi hodí.

Halda může vypadat například takto:

Halda – Heapsort

Samozřejmě si můžeme definovat speciální vlastnost haldy obráceně a mít v kořeni minimum, i to se používá.

Protože obvykle chceme třídit pole a ne haldu, musíme si z tohoto pole haldu nejprve postavit. Teď jistě očekáváte, že si vytvoříme stromovou strukturu pomocí ukazatelů nebo referencí a do ní budeme prvky přidávat. Haldu lze však malým trikem (díky jejímu vyvážení) reprezentovat v obyčejném poli, nebudeme tedy potřebovat žádnou pomocnou strukturu ani paměť. Budeme pracovat přímo v našem poli, na které se budeme dívat jako na haldu a můžeme tedy třídit rovnou na místě.

Halda v obrázku výše by v poli vypadala takto (nahoře indexy prvků, dole prvky):

0 1 2 3 4 5 6 7 8 9
9 7 8 5 4 0 3 2 1 2
Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!

Všimněte si, že zhaldované pole nemá moc společného s polem setříděným. Teď si ukážeme, jak s tímto polem pracovat jako s haldou. Jistě jste si všimli, že prvky v poli jsou prvky tak, jak jsou v haldě, seřazené shora dolů a zleva doprava. Když budeme chtít přistoupit ke kořeni, jednoduše sáhneme na index 0, poslední prvek haldy je také na indexu posledního prvku pole. Budeme však potřebovat přístup z libovolného otce do jeho synů a také ze syna k jeho otci.

Pokud bude mít syn index i, index jeho otce vypočítáme jako (i - 1) / 2 (dělení je celočíselné). Pokud bude mít otec index i, jeho levý syn bude mít index (2 * i + 1) a pravý syn (2 * i) + 2.

Můžeme si rychle ověřit, že to funguje. Zkusíme najít syna prvku 7, ten má index 1 (pole je indexováno od 0 a je druhý). (1 - 1) / 2 je 0, jeho otec je tedy prvek 9, což sedí. Jeho synové budou (2 * 1 + 1) = 3 a na třetím indexu je pětka - opravdu jeho levý syn. Pravý syn má index o jednu větší a opravdu je na něm prvek 4.

Máme tedy potřebné nástroje a můžeme se pustit do prvního kroku algoritmu - zhaldování pole.

Průběh

Zhaldování pole (postavení haldy)

Máme pole následujících prvků:

3 2 5 1 9 4

Pole nám reprezentuje následující "haldu":

Zhaldování pole – postavení haldy – Heapsort

Uvozovky jsem použil záměrně, protože tato halda je rozbitá - neplatí nám speciální vlastnost haldy. Musíme ji tedy opravit a pole zhaldovat. Použijeme k tomu funkci up (nahoru), kterou budeme postupně volat na prvky od kořene dolů. Funkce zjistí, jestli daný prvek neporušuje speciální vlastnost haldy (tedy pokud není větší než jeho otec) a pokud je, prvek s otcem prohodí. Tím se však může stát, že se stejný problém přenese o úroveň výše, proto se funkce opakuje, dokud speciální vlastnost haldy pro daný prvek neplatí nebo dokud nedojedeme do kořene. Funkci voláme pro každý prvek dokud nedojedeme nakonec, pak si můžeme být jisti, že jsme haldu opravili.

Z důvodu úspory místa v článku jen popíši průběh zhaldování, dívejte se přitom na obrázek výše. Můžete se také podívat na video níže, kde je to podrobně znázorněno.

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ě:

9 5 4 1 2 3
Zhaldované pole – postavení haldy – Heapsort

Můžeme tedy přistoupit k samotnému třídění.

Třídění

Jak jsem se již zmínil, budeme provádět vlastně Selection sort v haldě, budeme tedy prohazovat maximum s posledním prvkem, potom další druhé maximum s předposledním atd. Maximum leží vždy na indexu 0, takže ho nalezneme v konstantním čase. Prohození také žádný čas nezabere.

Menší problém tu však bude - prohozením prvků si totiž zcela jistě haldu rozbijeme. Původního maxima vzadu si již sice všímat nebudeme (je to již setříděná část pole, které si stejně jako v Selection sortu nevšímáme), ale prvek, který je nyní novým kořenem, dost pravděpodobně nebude maximum. Haldu opravíme podobnou funkci jako up, tentokrát funkcí down (dolů). Tu pustíme na kořen a pokud je některý se synů větší než otec, tak ho s otcem prohodíme. Pokud jsou větší oba, prohodíme otce s větším synem. Podobně jako u funkce up, i zde se nám problém může posunou dolů, proto se znovu podíváme na syna (nyní již otce) a zjistíme, zda je větší než jeho synové. Proces opakujeme, dokud platí speciální vlastnost haldy nebo dokud dojedeme do poslední úrovně. Tuto funkci musíme zavolat po každém prohození kořene s posledním prvkem.

Když se zamyslíme, zjistíme, že odtržení maxima nás nestojí vůbec nic, prohození také ne. Jediný časový problém je s funkcí down, která se bude provádět n krát (pro každé maximum) a v každém svém zavolání se bude opakovat maximálně log n krát (protože halda je vyvážený binární strom, má výšku log n, kde základ logaritmu je 2, protože každý vrchol má 2 syny. Funkce prověřuje jeden prvek v každém patře, v nejhorším případě tedy projede všechna patra, kterých je log n). U funkce up je časová složitost je, jako u funkce down, tedy opět O(n log n). Celkově zavoláme jednou funkci up a funkci down poté n krát, tedy výsledná časová složitost heapsortu je O(n log n).

Oproti dříve zmíněným algoritmům jsme si výrazně polepšili a zrychlení na větších polích je obrovské. Algoritmus však není stabilní, takže náročné uspokojí až Merge sort nebo Quicksort.

Vlastnosti algoritmu

Časová složitost O (n log n)
Stabilita Ne
Rychlost Velmi dobrá

Pozn. je myšlena časová složitost průměrného případu a rychlost vzhledem ke všem třídícím algoritmům

Vizualizace

Video ukázka

Sestavení haldy z pole

Z nějakého důvodu se nám pokazila halda a v druhém videu je v ní chyba (malé zaváhání a následná oprava). Na běhu algoritmu to nic nemění :)

Aplikování algoritmu na zhaldované pole

Zdrojový kód

  • //oprava haldy nahoru
    public static void up(int[] list, int i) {
      int child = i; //ulozim syna
      int parent, temp;
      while (child != 0) {
      parent = (child - 1) / 2; //otec
      if (list[parent] < list[child]) { //detekce chyby
        temp = list[parent]; //prohozeni syna s otcem
        list[parent] = list[child];
        list[child] = temp;
        child = parent; //novy syn
      }
      else
        return; //ok
      }
    }
    
    //oprava haldy dolu
    public static void down(int[] list, int last) {
      int parent = 0;
      int child, temp;
      while (parent * 2 + 1 <= last) {
        child = parent * 2 + 1;
        // pokud je vybran mensi syn
        if ((child < last) && (list[child] < list[child + 1]))
        child++; //vybereme toho vetsiho
        if (list[parent] < list[child]) { //detekce chyby
          temp = list[parent]; //prohozeni syna s otcem
          list[parent] = list[child];
          list[child] = temp;
          parent = child; //novy otec
        }
        else
          return;
        }
    }
    
    // postaveni haldy z pole
    public static void heapify(int[] list) {
      for (int i = 1; i < list.length; i++)
      up(list, i);
    }
    
    // samotne trideni
    public static void heapsort(int[] list) {
      heapify(list);
      int index = list.length - 1; // posledni prvek
      int temp;
      while (index > 0) {
        temp = list[0]; // prohození posledního prvku s maximem
        list[0] = list[index];
        list[index] = temp;
        index -= 1; //nastaveni noveho posledniho prvku
        down(list, index);
      }
    }
  • //oprava haldy nahoru
    public static void up(int[] list, int i) {
      int child = i; //ulozim syna
      int parent, temp;
      while (child != 0) {
        parent = (child - 1) / 2; //otec
        if (list[parent] < list[child]) { //detekce chyby
          temp = list[parent]; //prohozeni syna s otcem
          list[parent] = list[child];
          list[child] = temp;
          child = parent; //novy syn
        }
        else
          return; //ok
        }
    }
    
    //oprava haldy dolu
    public static void down(int[] list, int last) {
      int parent = 0;
      int child, temp;
      while (parent * 2 + 1 <= last) {
        child = parent * 2 + 1;
        //pokud je vybran mensi syn
        if ((child < last) && (list[child] < list[child + 1]))
        child++; //vybereme toho vetsiho
        if (list[parent] < list[child]) { //detekce chyby
          temp = list[parent]; //prohozeni syna s otcem
          list[parent] = list[child];
          list[child] = temp;
          parent = child; //novy otec
        }
        else
          return;
        }
    }
    
    // postaveni haldy z pole
    public static void heapify(int[] list) {
      for (int i = 1; i < list.Length; i++)
      up(list, i);
    }
    
    // samotne trideni
    public static void heapsort(int[] list) {
      heapify(list);
      int index = list.Length - 1; //posledni prvek
      int temp;
      while (index > 0) {
        temp = list[0]; // prohození posledního prvku s maximem
        list[0] = list[index];
        list[index] = temp;
        index -= 1; //nastaveni noveho posledniho prvku
        down(list, index);
      }
    }
  • // oprava haldy nahoru
    procedure up(var list: array of integer; i: integer);
    var parent, child, temp: integer;
    begin
      child:=i; // ulozim syna
      while (child <> 0) do begin
        parent:=(child - 1) div 2; // otec
        if (list[parent] < list[child]) then begin // detekce chyby
          temp:=list[parent]; // prohozeni syna s otcem
          list[parent]:=list[child];
          list[child]:=temp;
          child:=parent; // novy syn
        end
        else exit; // OK
      end;
    end;
    
    // oprava haldy dolu
    procedure down(var list: array of integer; last: integer);
    var parent, child, temp: integer;
    begin
      parent:=0;
      while (parent * 2 + 1 <= last) do begin
        child:=parent * 2 + 1;
        // pokud je vybran mensi syn
        if ((child < last) and (list[child] < list[child + 1])) then
        inc(child); // vybereme toho vetsiho
        if (list[parent] < list[child]) then begin // detekce chyby
          temp:=list[parent]; // prohozeni syna s otcem
          list[parent]:=list[child];
          list[child]:=temp;
          parent:=child; // novy otec
        end else exit;
      end;
    end;
    
    // postaveni haldy z pole
    procedure heapify(var list: array of integer);
    var i: integer;
    begin
      for i:=1 to (length(list) - 1) do
      up(list, i);
    end;
    
    // samotne trideni
    procedure heapsort(var list: array of integer);
    var temp, index: integer;
    begin
      heapify(list);
      index:=length(list) - 1; // posledni prvek
      while (index > 0) do begin
        temp:=list[0]; // prohozeni posledniho prvku s maximem
        list[0]:=list[index];
        list[index]:=temp;
        dec(index); // nastaveni noveho posledniho prvku
        down(list, index);
      end;
    end;
  • # oprava haldy nahoru
    def up(list, i)
      child = i # ulozim syna
      while (child != 0)
        parent = (child - 1) / 2 # otec
        if (list[parent] < list[child]) # detekce chyby
          temp = list[parent] # prohozeni syna s otcem
          list[parent] = list[child]
          list[child] = temp
          child = parent # novy syn
        else
          return # OK
        end
      end
    end
    
    # oprava haldy dolu
    def down(list, last)
      parent = 0
      while (parent * 2 + 1 <= last)
        child = parent * 2 + 1
        # pokud je vybran mensi syn
        if ((child < last) && (list[child] < list[child + 1]))
          child += 1 # vybereme toho vetsiho
        end
        if (list[parent] < list[child]) # detekce chyby
          temp = list[parent] # prohozeni syna s otcem
          list[parent] = list[child]
          list[child] = temp
          parent = child # novy otec
        else
          return
        end
      end
    end
    
    # postaveni haldy z pole
    def heapify(list)
      1.upto(list.length - 1) { |i| up(list, i) }
    end
    
    # samotne trideni
    def heapsort(list)
      heapify(list)
      index = list.length - 1 # posledni prvek
      while (index > 0)
        temp = list[0] # prohozeni posledniho prvku s maximem
        list[0] = list[index]
        list[index] = temp
        index -= 1 # nastaveni noveho posledniho prvku
        down(list, index)
      end
    end

Implementace tohoto algoritmu je založena na materiálech Unicorn College od profesora Ondřeje Kučery.


 

Všechny články v sekci
Třídící/řadící algoritmy
Článek pro vás napsal David Čápka
Avatar
Jak se ti líbí článek?
10 hlasů
Autor pracuje jako softwarový architekt a pedagog na projektu ITnetwork.cz (a jeho zahraničních verzích). Velmi si váží svobody podnikání v naší zemi a věří, že když se člověk neštítí práce, tak dokáže úplně cokoli.
Unicorn university Autor sítě se informační technologie naučil na Unicorn College - prestižní soukromé vysoké škole IT a ekonomie.
Aktivity (6)

 

 

Komentáře

Avatar
Martin Dráb
Redaktor
Avatar
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:

  1. Prvky na nejhlubší hladině (je jich až n/2) nemají žádné potomky, tedy netřeba s nimi nic provádět.
  2. 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.
  3. 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
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Martin Dráb
David Čápka: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(n2). 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(n2), 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
Jsem moc rád, že jsi na síti, a přeji ti top IT kariéru, ať jako zaměstnanec nebo podnikatel. Máš na to! :)
Avatar
prasopes
Neregistrovaný
Avatar
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
Avatar
Odpovídá na David Čápka
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
Avatar
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
Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!
Avatar
Jan Troják
Brigádník
Avatar
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
Avatar
karolko
Člen
Avatar
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
Avatar
krepsy3
Redaktor
Avatar
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.
Avatar
Peter Večera
Brigádník
Avatar
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.