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

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

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

{PHP}
// 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);
  }
}


$list = [17, 1, 3, 28, 8, 7, 4, 2];
heapsort($list);
print_r($list);

{/PHP}

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.

Článek pro vás napsal David Hartinger

Uživatelské hodnocení:

69 hlasů

David je zakladatelem ITnetwork a programování se profesionálně věnuje 15 let. Má rád Nirvanu, nemovitosti a svobodu podnikání.

David se informační technologie naučil na Unicorn University - prestižní soukromé vysoké škole IT a ekonomie.

Aktivity

Nejčastěji vyhledáváné