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:

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

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:

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

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

Vizualizácia

Video ukážka

Zostavenie haldy z poľa

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