====== Heap sort ======

Třídění haldou, skripta 5.1.6

Heap sort má složitost O(n log n), kde n je počet tříděných prvků


===== Formální rozložení prvků ve stromu =====

Je zadáno pole N hodnot a[0], ... a[N-1]. \\
Hodnoty boudou stále uloženy v poli, ale představíme si je ve stromu. \\
Do kořene stromu umístíme a[0]. \\
Do patra pod kořenem umístíme a[1] , a[2]. \\
O patro níže a[3], a[4], a[5], a[6]. \\
Následující patra budou mít 8, 16, 32, 64, ... prvků. \\
Dolní patro nemusí být kompletní. 

<code>
   .------------------------------------------.
   | a[0] |  a[1] | a[2] | a[3] | a[4] | a[5] |
   .------------------------------------------.
</code>

<code>
                    a[0]
                     |
         .-------------------------.
         |                         |
        a[1]                      a[2]
         |                         |
    .----------.              .---------.      
    |          |              |
   a[3]       a[4]           a[5]

</code>

Pod prvkem **a[i]** jsou prvky **a[2i+1]** , **a[2i+2]**. \\
( Pole **a** indexujeme od **0**. ) \\
( Pokud v jinem jazyce indexujeme od **1**, tak pod prvkem a[i] jsou prvky a[2i] , a[2i+1]. )

<code>
                    a[i]
                     |
            .-----------------.
            |                 |
         a[2i+1]           a[2i+2]
</code>


===== Halda =====

V poli si vybereme posloupnost prvku s indexy **i**, **i+1**, ..., **k**. 

Řekneme, že prvky **a[i]**, **a[i+1]**,  ..., **a[k]** tvoří **haldu**, \\
pokud pro všechny hrany stromu spojující prvky a[i], a[i+1], ..., a[k] \\
je prvek na horním konci hrany **větší nebo roven** než prvek na dolním konci hrany.

Tj. vybereme si několik za sebou jdoucích prvků v poli ( tato posloupnost může být i jedno-prvková nebo prázdná ). \\
Uvažujeme jen hrany spojující prvky v této posloupnosti (hrany které začínají nebo končí mimo tuto posloupnost nás nezajímají ). 

Vezmeme prvek **a[t]**, index t je z naší posloupnosti **i < = t < = k**. \\
Pod prvkem **a[t]** mohou být prvky **a[2t+1]** , **a[2t+2]**. \\
Pokud **2t+1 < = k**, levý pod-prvek je součástí naší posloupnosti a požadujeme **a[t] > = a[2t+1]**. \\
Pokud **2t+2 < = k**, tak i pravý pod-prvek je z naší posloupnosti a požadujeme **a[t] > = a[2t+2]**. \\

===== Vytvoření haldy =====

Funkce **heapify** pracuje s posloupností prvků a[i], ... a[k]. \\
Na vstupu do funkce, předpokládáme, že a[**i+1**], ... a[k] již tvoří haldu. \\
Cheme celou posloupnost a[i], ... a[k] proměnit v haldu.

Vezmeme si nejvýše položený prvek **a[i]**, ten zatím nemusí splňovat požadavek na haldu. \\
Hodnotu a[i] porovnáme s hodnotami podřízených prvků (pokud podřízené prvky v rámci a[i], ... a[k] existují) \\
Pokud je a[i] větší nebo roven než podřízené prvky, je vše v pořádku. Následující prvky již haldu tvoří, můžeme funkci ukončit. \\
Jinak vybereme větší z podřízených prvků, jeho hodnotu prohodíme s hodnotou nadřízeného prvku a pokračujeme stejným postupem na místě podřízeného prvku. 

Obrázek http://cdn.programiz.com/sites/tutorial2program/files/heapify-base-case.jpg

Hodnota a[i] původně na vrcholu vybrané části stromu padá dolů, \\
až pod ní budou prvky, které ji nepřevyšují, \\
nebo až je na nejnižším patře vybrané části stromu.

Obrázek http://cdn.programiz.com/sites/tutorial2program/files/heapfy-root-element-when-subtrees-are-max-heaps.jpg



==== Cyklus od vrcholu posloupnosti dolů ====

Začneme s prvkem a[i], pokud půjdeme níže, budeme měnit proměnnou **i**.

Cyklus, který kontroluje, zda je pod a[i] alespoň levý prvek.
<code C++>
    while (2*i+1 <= k) 
</code>

Poznamenáme si index levého prvku do nové proměnné **v**.
<code C++>
        int v = 2*i+1;
</code>

==== Výběr většího podřízeného prvku ====

Zkusíme zda existuje také pravý prvek. \\
Pokud existuje porovnáme s levým prvkem. \\
Do proměnné **v** uložíme index většího pod-prvku. ( a víme, že **v** je z uzavřeného intervalu **i**, ... **k** )

<code C++>
        if (v+1 <= k)
            if (a[v+1] > a[v])
                v = v + 1;
</code>



==== Prohození prvků ====

Nyní porovnáme **a[i]** ("horní prvek") s prvkem **a[v]** ("vítězný podřízený prvek"). \\
Pokud je a[i] menší, prohodíme hodnoty ulořené v a[i] a a[v] a pokračujeme na místě podřízeného prvku (kde je nyní hodnota padající ze shora ).

<code C++>
        if (a[i] < a[v])
        {
            swap (a[i], a[v]);
            i = v;
        }
</code>


==== Funkce swap ====

Funkce **swap** dostane jako parametry **x** a **y** odkazy (**&**) na dvě celá čísla, která má prohodit. \\
V našem případě dostane odkazy na dva prvky pole **a[i]** , **a[v]** \\
Klíčové slovo inline doporučuje překladači nevolat podprogram, ale potřebné instrukce vložit v místě volání funkce.

<code C++>
inline void swap (int & x, int & y)
{
    int t = x;
    x = y;
    y = t;
}
</code>

Parametry předávané odkazem jsem již potkali [[zalg:strom_add#vkladani_prvku_do_stromu|vkládaní prvku do stromu]]


==== Altertativní funce swap pracující s globálním polem a parametrem jsou indexy v poli ====
<code C++>
inline void alt_swap (int i, int k)
{
    int t = a[i];
    a[i] = a[k];
    a[k] = t;
}
</code>

Na místo původního volání funkce **swap (a[i], a[v])** použijeme

<code C++>
    alt_swap (i, v);
</code>



==== Ukončení cyklu ====

Nastavíme proměnnou **i** na příliš velkou hodnotu, která zastaví **while** cyklus.

<code C++>
  else
  {
     i = k+1; 
  }
</code>

==== Celá funkce heapify ====

<code C++>
void heapify (int i, int k)
{
    while (2*i+1 <= k)
    {
        int v = 2*i+1;

        if (v+1 <= k)
            if (a[v+1] > a[v])
                v = v + 1;

        if (a[i] < a[v])
        {
            swap (a[i], a[v]);
            i = v;
        }
        else
        {
            i = k+1; // ukonceni cyklu
        }
    }
}
</code>

:!: Počet prováděných instrukcí je úměrný výšce stromu s vybranými prvky a[i], ... a[k].

Pro ilustraci: \\
http://www.youtube.com/watch?v=HqPJF2L5h9U \\
http://www.youtube.com/watch?v=B7hVxCmfPtM (indexují od 1 ) \\





===== Třídění =====

Nejprve o uspořádání prvků v poli nic nevíme.

==== Vytváříme haldu - od konce pole k prvnímu prvku ====

Jednoprvková posloupnost s indexy **n-1, ... n-1** je z definice haldou. \\
Přidáme jeden prvek a použijeme funkci **heapify** na dvojprvkovou posloupnost s indexy **n-2, ... n-1**. \\
Budeme přidávat prvky na začátek, funkci **heapify** upravovat hodnoty, aby tvořily haldu.

<code C++>
    for (int i = n-1; i >= 0; i--)
        heapify (i, n-1); 
</code>

Použijeme heapify (i, n-1) pro i = n-1, n-2, ..., 2, 1, 0. \\
Pro mnoho hodnot bude posloupnost umístěna v dolním patře. \\
Nebo bude v dolních dvou patrech, ale nebude obsahovat hranu. \\
Můžete se podívat na **while (2*i+1 <= k)**, kde **k=n-1** a pozměnit počáteční hodnotu **for** cyklu.



==== Odebereme první největší prvek, uložíme na konec pole ====

Celá posloupnost a[0], ... a[n-1] tvoří haldu. \\
Tedy a[0] je největší prvek, uložíme ho na konec pole. \\
Prvek, který byl na konci pole zkusíme umístit do a[0]. \\
Nově umístěný prvek necháme spadnout na správné místo. \\
Haldu od konce postupně zkracujeme, jsou tam umístěny již setříděné hodnory, které nechceme znovu zamíchat do třídění.

<code C++>
    for (int i = n-1; i > 0; i--) 
    {
        swap (a[0], a[i]); // odebrat hodnotu z vrcholu a umistit na soucasny konec
        heapify (0, i-1);  // zbyle hodnoty opravit, aby opet tvorily haldu
    }
</code>


Obrázek http://stackoverflow.com/questions/41212072/ascending-and-descending-heapsort \\
Zeleně jsou zobrazeny uložené/setříděné hodnoty. \\
Červeně prohazované/nově nasazené hodnoty. \\
Žlutě je nakreslena zmenšující se halda.

==== Funkce heapsort ====

<code C++>
void heapsort (int n)
{
    for (int i = n-1; i >= 0; i--)
        heapify (i, n-1);

    for (int i = n-1; i > 0; i--) 
    {
        swap (a[0], a[i]);
        heapify (0, i-1);
    }
}
</code>

:!: Počet instrukcí funkce heapify je úměrný výšce stromu. \\
Výšku stromu shora odhadneme logaritmem o základu 2 z počtu prvků (zvětšeným o 1). \\
Oba **for** cykly proběhnou **n**-krát. \\
Celkem O (n log n)

===== Vstupní hodnoty, tisk a kontrola hodnot =====


<code C++>
    srand (time (nullptr));
    for (int i = 0; i < N; i++)
        a[i] = rand() % 10000;

    heapsort (N); // trideni

    bool ok = true;
    for (int i = 0; i < N; i++)
    {
        cout << a[i];
        if (i < N-1 && a[i + 1] < a[i]) { ok = false; cout << " CHYBA"; }
        cout << endl;
    }
</code>


===== Celý program =====

<code C++>
#include <iostream>
#include <time.h>
using namespace std;

const int N = 1000000;

int a[N];

inline void swap (int & x, int & y)
{
    int t = x;
    x = y;
    y = t;
}

void heapify(int i, int k)
// vytvorit hromadu z a[i] ... a[k]
// za predpokladu, ze a[i+1] ... a[k] jiz hromadu tvori
{
    while (2 * i + 1 <= k)
    {
        int v = 2 * i + 1;

        if (v + 1 <= k)
            if (a[v+1] > a[v])
                v = v + 1;

        if (a[i] < a[v])
        {
            swap (a[i], a[v]);
            i = v;
        }
        else
        {
            i = k+1; // ukonceni cyklu
        }
    }
}

void heapsort (int n)
// setridit a[0] ... a[n-1]
{
    for (int i = n-1; i >= 0; i--)
        heapify (i, n-1);

    for (int i = n-1; i > 0; i--) 
    {
        swap (a[0], a[i]);
        heapify (0, i-1);
    }
}

int main()
{
    srand (time (nullptr));
    for (int i = 0; i < N; i++)
        a[i] = rand() % 10000;

    heapsort (N);

    bool ok = true;
    for (int i = 0; i < N; i++)
    {
        cout << a[i];
        if (i < N-1 && a[i + 1] < a[i]) { ok = false; cout << " CHYBA"; }
        cout << endl;
    }

    if (ok)
       cout << "O.K." << endl; 
}
</code>

Mini literatura: http://cs.wikipedia.org/wiki/%C5%98azen%C3%AD_haldou