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ů

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í.

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

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

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]. )

                    a[i]
                     |
            .-----------------.
            |                 |
         a[2i+1]           a[2i+2]

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].

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

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.

    while (2*i+1 <= k)

Poznamenáme si index levého prvku do nové proměnné v.

        int v = 2*i+1;

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 )

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

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

        if (a[i] < a[v])
        {
            swap (a[i], a[v]);
            i = v;
        }

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.

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

Parametry předávané odkazem jsem již potkali vkládaní prvku do stromu

inline void alt_swap (int i, int k)
{
    int t = a[i];
    a[i] = a[k];
    a[k] = t;
}

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

    alt_swap (i, v);

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

  else
  {
     i = k+1; 
  }

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
        }
    }
}

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 )

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

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.

    for (int i = n-1; i >= 0; i--)
        heapify (i, n-1);

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.

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í.

    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
    }

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.

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);
    }
}

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)

    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;
    }

#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; 
}

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