Heapsort

Algoritmy Třídění 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

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

Video ukázka

Stavění 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í, až budeme moct, přetočíme to :)

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 parrent, temp;
  while (child != 0) {
  parrent = (child - 1) / 2; //otec
  if (list[parrent] < list[child]) { //detekce chyby
    temp = list[parrent]; //prohozeni syna s otcem
    list[parrent] = list[child];
    list[child] = temp;
    child = parrent; //novy syn
  }
  else
    return; //ok
  }
}

//oprava haldy dolu
public static void down(int[] list, int last) {
  int parrent = 0;
  int child, temp;
  while (parrent * 2 + 1 <= last) {
    child = parrent * 2 + 1;
    // pokud je vybran mensi syn
    if ((child < last) && (list[child] < list[child + 1]))
    child++; //vybereme toho vetsiho
    if (list[parrent] < list[child]) { //detekce chyby
      temp = list[parrent]; //prohozeni syna s otcem
      list[parrent] = list[child];
      list[child] = temp;
      parrent = 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 parrent, temp;
  while (child != 0) {
    parrent = (child - 1) / 2; //otec
    if (list[parrent] < list[child]) { //detekce chyby
      temp = list[parrent]; //prohozeni syna s otcem
      list[parrent] = list[child];
      list[child] = temp;
      child = parrent; //novy syn
    }
    else
      return; //ok
    }
}

//oprava haldy dolu
public static void down(int[] list, int last) {
  int parrent = 0;
  int child, temp;
  while (parrent * 2 + 1 <= last) {
    child = parrent * 2 + 1;
    //pokud je vybran mensi syn
    if ((child < last) && (list[child] < list[child + 1]))
    child++; //vybereme toho vetsiho
    if (list[parrent] < list[child]) { //detekce chyby
      temp = list[parrent]; //prohozeni syna s otcem
      list[parrent] = list[child];
      list[child] = temp;
      parrent = 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 parrent, child, temp: integer;
begin
  child:=i; // ulozim syna
  while (child <> 0) do begin
    parrent:=(child - 1) div 2; // otec
    if (list[parrent] < list[child]) then begin // detekce chyby
      temp:=list[parrent]; // prohozeni syna s otcem
      list[parrent]:=list[child];
      list[child]:=temp;
      child:=parrent; // novy syn
    end
    else exit; // OK
  end;
end;

// oprava haldy dolu
procedure down(var list: array of integer; last: integer);
var parrent, child, temp: integer;
begin
  parrent:=0;
  while (parrent * 2 + 1 <= last) do begin
    child:=parrent * 2 + 1;
    // pokud je vybran mensi syn
    if ((child < last) and (list[child] < list[child + 1])) then
    inc(child); // vybereme toho vetsiho
    if (list[parrent] < list[child]) then begin // detekce chyby
      temp:=list[parrent]; // prohozeni syna s otcem
      list[parrent]:=list[child];
      list[child]:=temp;
      parrent:=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)
    parrent = (child - 1) / 2 # otec
    if (list[parrent] < list[child]) # detekce chyby
      temp = list[parrent] # prohozeni syna s otcem
      list[parrent] = list[child]
      list[child] = temp
      child = parrent # novy syn
    else
      return # OK
    end
  end
end

# oprava haldy dolu
def down(list, last)
  parrent = 0
  while (parrent * 2 + 1 <= last)
    child = parrent * 2 + 1
    # pokud je vybran mensi syn
    if ((child < last) && (list[child] < list[child + 1]))
      child += 1 # vybereme toho vetsiho
    end
    if (list[parrent] < list[child]) # detekce chyby
      temp = list[parrent] # prohozeni syna s otcem
      list[parrent] = list[child]
      list[child] = temp
      parrent = 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.


 

  Aktivity (1)

Článek pro vás napsal David Čápka
Avatar
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 College Autor se informační technologie naučil na Unicorn College - prestižní soukromé vysoké škole IT a ekonomie.

Jak se ti líbí článek?
Celkem (9 hlasů) :
4.777784.777784.777784.777784.77778


 


Miniatura
Předchozí článek
Insertion sort
Miniatura
Všechny články v sekci
Třídící/řadící algoritmy
Miniatura
Následující článek
Merge Sort

 

 

Komentáře

Avatar
Martin Dráb
Redaktor
Avatar
Martin Dráb:

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  +1 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:

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
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
prasopes
Neregistrovaný
Avatar
prasopes:

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:

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:

Dakujem za clanok a vysvetlenie velmi mi pomohli. Autorovi patri obrovska vdaka.

 
Odpovědět 29. června 21:21
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 5 zpráv z 5.