IT rekvalifikace s garancí práce. Seniorní programátoři vydělávají až 160 000 Kč/měsíc a rekvalifikace je prvním krokem. Zjisti, jak na to!
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í.

Lekce 4 - Heapsort

V minulé lekci, Insertion sort, jsme si ukázali algoritmus Insertion sort i se zdrojovými kódy.

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 - Třídicí/řadicí algoritmy

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

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 - Třídicí/řadicí algoritmy

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 - Třídicí/řadicí algoritmy

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
  • // oprava haldy nahoru
    function up(array &$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
        }
    }
    
    //oprava haldy dolu
    function down(array &$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++; // 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
    function heapify(array &$list) {
      for ($i = 1; $i < count($list); $i++)
      up($list, $i);
    }
    
    // samotne trideni
    function heapsort(array &$list) {
      heapify($list);
      $index = count($list) - 1; // posledni prvek
      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);
      }
    }
    
    

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

V další lekci, Merge Sort, si ukážeme algoritmus Merge sort i se zdrojovými kódy.


 

Předchozí článek
Insertion sort
Všechny články v sekci
Třídicí/řadicí algoritmy
Přeskočit článek
(nedoporučujeme)
Merge Sort
Článek pro vás napsal David Hartinger
Avatar
Uživatelské hodnocení:
56 hlasů
David je zakladatelem ITnetwork a programování se profesionálně věnuje 15 let. Má rád Nirvanu, nemovitosti a svobodu podnikání.
Unicorn university David se informační technologie naučil na Unicorn University - prestižní soukromé vysoké škole IT a ekonomie.
Aktivity