Pouze tento týden sleva až 80 % na e-learning týkající se C# .NET. Zároveň využij akci až 30 % zdarma při nákupu e-learningu - Více informací.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.
C# week + discount 30

Heapsort

Heapsort patrí medzi chytré algoritmy, ktoré sú rádovo rýchlejšie ako tie doteraz spomínané. Stavia na myšlienkach algoritme Selection sort a je teda založený na odtrhávanie extrému (v tomto prípade maxima), ktoré vždy presúva na koniec poľa. Po začlenení všetkých maxím na koniec máme určite pole zotriedené. Problém Selection sortu však bol práve vo hľadanie maxima alebo minima. V každom vonkajšom cykle sa celá Hlavička časť poľa musela prejsť a každý prvok skontrolovať, či nie je náhodou hľadaným maximom. V poli maximum rýchlejšie asi nenájdeme.

Ale čo keby existovala dátová štruktúra, v ktorej by sme mohli prvky reprezentovať rovnako, ako v poli, a zároveň sme maximum našli v konštantnom čase, bez jediného priechodu? Keď sa takto pýtam, asi vám je už jasné, že štruktúra existovať bude. Nazýva sa Halda (anglicky Heap, preto Heap sort čiže triedenie haldou).

Halda je binárnym stromom s nasledujúcimi vlastnosťami:

  • Všetky "poschodia" haldy až na poslednú sú plne obsadené prvky (teda každý vnútorný vrchol má práve 2 synov, strom je veľmi vyvážený)
  • Posledné poschodie haldy je zaplnené zľava (môže byť aj zaplnené celé)
  • Pre prvky v halde platí tzv. Špeciálna vlastnosť haldy: obaja synovia sú vždy menšie alebo rovné otcovi.

Zo špeciálne vlastnosti haldy nutne vyplýva, že v koreni bude vždy uložené maximum, čo sa nám veľmi hodí.

Halda môže vyzerať napríklad takto:

Halda – Heapsort

Samozrejme si môžeme definovať špeciálnu vlastnosť haldy obrátene a mať v koreni minimum, aj to sa používa.

Pretože zvyčajne chceme triediť poľa a nie haldu, musíme si z tohto poľa haldu najprv postaviť. Teraz iste očakávate, že si vytvoríme stromovú štruktúru pomocou ukazovateľov alebo referencií a do nej budeme prvky pridávať. Haldu možno však malým trikom (vďaka jej vyváženie) reprezentovať v obyčajnom poli, nebudeme teda potrebovať žiadnu pomocnú štruktúru ani pamäť. Budeme pracovať priamo v našom poli, na ktoré sa budeme pozerať ako na haldu a môžeme teda triediť rovno na mieste.

Halda v obrázku vyššie by v poli vyzerala takto (hore indexy prvkov, dole prvky):

0 1 2 3 4 5 6 7 8 9
9 7 8 5 4 0 3 2 1 2
Všimnite si, že zhaldované pole nemá veľa spoločného s poľom setříděným. Teraz si ukážeme, ako s týmto poľom pracovať ako s haldou. Iste ste si všimli, že prvky v poli sú prvky tak, ako sú v halde, zoradené zhora nadol a zľava doprava. Keď budeme chcieť pristúpiť ku koreňu, jednoducho siahneme na index 0, posledný prvok haldy je tiež na indexe posledného prvku poľa. Budeme však potrebovať prístup z ľubovoľného otca do jeho synov a tiež zo syna k jeho otcovi.

Pokiaľ bude mať syn index i, index jeho otca vypočítame ako (i - 1) / 2 (delenie je celočíselné). Pokiaľ bude mať otec index i, jeho ľavý syn bude mať index (2 * i + 1) a pravý syn (2 * i) + 2.

Môžeme si rýchlo overiť, že to funguje. Skúsime nájsť syna prvku 7, ten má index 1 (pole je indexované od 0 a je druhý). (1 - 1) / 2 je 0, jeho otec je teda prvok 9, čo sedí. Jeho synovia budú (2 * 1 + 1) = 3 a na treťom indexu je päťka - naozaj jeho ľavý syn. Pravý syn má index o jednu väčšiu a naozaj je na ňom prvok 4.

Máme teda potrebné nástroje a môžeme sa pustiť do prvého kroku algoritmu - zhaldování poľa.

Priebeh

Zhaldování pole (postavenie haldy)

Máme pole nasledujúcich prvkov:

3 2 5 1 9 4
Pole nám reprezentuje nasledujúce "haldu":
Zhaldování pole – postavenie haldy – Heapsort

Úvodzovky som použil zámerne, pretože táto halda je rozbitá - neplatí nám špeciálna vlastnosť haldy. Musíme ju teda opraviť a polia zhaldovat. Použijeme na to funkciu up (hore), ktorú budeme postupne volať na prvky od koreňa dole. Funkcia zistí, či daný prvok neporušuje špeciálnu vlastnosť haldy (teda ak nie je väčší ako jeho otec) a ak je, prvok s otcom prehodí. Tým sa však môže stať, že sa rovnaký problém prenesie o úroveň vyššie, preto sa funkcia opakuje, kým špeciálnu vlastnosť haldy pre daný prvok neplatí alebo kým nedôjde do koreňa. Funkciu voláme pre každý prvok dokiaľ nedôjde nakoniec, potom si môžeme byť istí, že sme haldu opravili.

Z dôvodu úspory miesta v článku len popíšem priebeh zhaldování, pozerajte sa pritom na obrázok vyššie. Môžete sa tiež pozrieť na video nižšie, kde je to podrobne znázornené.

Na prvý prvok (koreň, 3) funkciu up púšťať nebudeme, pretože ten žiadneho otca nemá. Začneme teda s prvkom 2, ten je menšia ako otec, necháme ho na mieste. Ďalšia je prvok 5, ten je väčší ako otec (3), preto ho s otcom prehodíme a sme už v koreni, takže končíme. Prvok 1 je menšia ako 2, to je v poriadku. 9 je však väčší ako 2, preto je prehodíme. 9 je však stále väčší ako 3, prehodíme teda znovu a 9 (maximum) sa dostáva do koreňa. 4 je väčší ako 3, preto prehodíme. 4 je potom menšia ako 9, to je už v poriadku. Zhaldované polia a halda, ktorú reprezentuje, vyzerajú nasledovne:

9 5 4 1 2 3
.<> Zhaldované pole – postavenie haldy – Heapsort

Môžeme teda pristúpiť k samotnému triedenia.

Triedenie

Ako som sa už zmienil, budeme vykonávať vlastne Selection sort v halde, budeme teda prehadzovať maximum s posledným prvkom, potom ďalšie druhé maximum s predposledným atď. Maximum leží vždy na indexe 0, takže ho nájdeme v konštantnom čase. Prehodenie tiež žiadny čas nezaberie.

Menší problém tu však bude - prehodením prvkov si totiž celkom iste haldu rozbijeme. Pôvodného maxima vzadu si už síce všímať nebudeme (je to už zotriedená časť poľa, ktoré si rovnako ako v Selection sortu nevšímame), ale prvok, ktorý je teraz novým koreňom, dosť pravdepodobne nebude maximum. Haldu opravíme podobnú funkciu ako up, tentoraz funkcií down (dole). Tú pustíme na koreň a ak je niektorý sa synov väčšie ako otec, tak ho s otcom prehodíme. Ak sú väčšie obaja, prehodíme otca s väčším synom. Podobne ako pri funkcii up, aj tu sa nám problém môže posunú nadol, preto sa znovu pozrieme na syna (teraz už otca) a zistíme, či je väčší ako jeho synovia. Proces opakujeme, kým platia špeciálne vlastnosť haldy alebo kým prídeme do poslednej úrovne. Túto funkciu musíme zavolať po každom prehodenie koreňa s posledným prvkom.

Keď sa zamyslíme, zistíme, že odtrhnutie maxima nás nestojí vôbec nič, prehodenie tiež nie. Jediný časový problém je s funkciou down, ktorá sa bude vykonávať n krát (pre každé maximum) a v každom svojom zavolaní sa bude opakovať maximálne log n krát (pretože halda je vyvážený binárny strom, má výšku log n, kde základ logaritmy je 2, pretože každý vrchol má 2 synov. Funkcia preveruje jeden prvok v každom poschodí, v najhoršom prípade teda prejde všetky poschodia, ktorých je log n). U funkcie up je časová zložitosť je, ako pri funkcii down, teda opäť O (n log n). Celkovo zavoláme raz funkciu up a funkciu down potom n krát, teda výsledná časová zložitosť heapsortu je O (n log n).

Oproti skôr zmieneným algoritmom sme si výrazne polepšili a zrýchlenie na väčších poliach je obrovské. Algoritmus však nie je stabilný, takže náročné uspokojí až Merge sort alebo Quicksort.

Vlastnosti algoritmu

časová zložitosť O (n log n)
stabilita nie
rýchlosť veľmi dobrá
Pozn. je myslená časová zložitosť priemerného prípadu a rýchlosť vzhľadom ku všetkým triediacim algoritmom

Vizualizácia

Video ukážka

Zostavenie haldy z poľa

Z nejakého dôvodu sa nám pokazila halda a v druhom videu je v nej chyba (malé zaváhanie a následná oprava). Na behu algoritmu to nič nemení :)

Aplikovanie 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
Implementácia tohto algoritmu je založená na materiáloch Unicorn College od profesora Ondreja Kučeru.

 

Všetky články v sekcii
Triediace / radiacej algoritmy
Článok pre vás napísal David Čápka
Avatar
Užívateľské hodnotenie:
Ešte nikto nehodnotil, buď prvý!
David je zakladatelem ITnetwork a programování se profesionálně věnuje 13 let. Má rád Nirvanu, sushi a svobodu podnikání.
Unicorn university David sa informačné technológie naučil na Unicorn University - prestížnej súkromnej vysokej škole IT a ekonómie.
Aktivity

 

 

Komentáre

Avatar
Martin Dráb
Tvůrce
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é...

Odpovedať
21.7.2011 1:08
2 + 2 = 5 for extremely large values of 2
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovedá 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 :)

Odpovedať
21.7.2011 9:30
One of the most common causes of failure is the habit of quitting when one is overtaken by temporary defeat.
Avatar
prasopes
Nevyplnené
Avatar
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
Avatar
Odpovedá 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

 
Odpovedať
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.

 
Odpovedať
29.6.2016 21:21
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)

Editované 12.8.2017 17:19
 
Odpovedať
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.

 
Odpovedať
28.3.2018 7:53
Avatar
krepsy3
Tvůrce
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ů :)

Editované 22.8.2018 16:54
Odpovedať
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.

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.

Zobrazené 9 správy z 9.