====== Heap sort (indexovani od 0) ======

<code C++>
#include <iostream>
#include <time.h>

using namespace std;

const int N = 1000;

int a [N];

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

void heapify (int i, int k)
// vytvorit haldu s indexy i, ..., k
// za predpokladu, ze indexy i+1, ..., k jiz haldu tvori
{
    while (2*i+1 <= k) // levy existuje
    {
        int v = 2*i+1; // index leveho 
        if (v+1 <= k) // pravy existuje
            if (a [v+1] > a [v])  // pravy je vetsi
                v = v+1; // index vetsiho

        if (a [v] > a [i]) // porovnani vetsiho a prvku nahore
        {
            swap (v, i); // prohodime
            i = v; // pokracujeme s indexem v
        }
        else
        {
            i = k; // zastavime cylus
        }
    }
}

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

    swap (0, n-1);

    for (int k = n-2; k >= 1; k--)
    {
        heapify (0, k);
        swap (0, k);
    }
}

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>

====== Heap sort (indexovani od 1) ======

<code C++>
#include <iostream>
#include <time.h>

using namespace std;

const int N = 1000;

int a [N+1]; // a[0] nepouzivam

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

void heapify (int i, int k)
// vytvorit haldu s indexy i, ..., k
// za predpokladu, ze indexy i+1, ..., k jiz haldu tvori
{
    while (2*i <= k) // levy existuje
    {
        int v = 2*i; // index leveho 
        if (v+1 <= k) // pravy existuje
            if (a [v+1] > a [v])  // pravy je vetsi
                v = v+1; // index vetsiho

        if (a [v] > a [i]) // porovnani vetsiho a prvku nahore
        {
            swap (v, i); // prohodime
            i = v; // pokracujeme s indexem v
        }
        else
        {
            i = k; // zastavime cylus
        }
    }
}

void heapSort (int n)
{
    for (int i = n; i >= 1; i--)
       heapify (i, n);

    swap (1, n);

    for (int k = n-1; k >= 2; k--)
    {
        heapify (1, k);
        swap (1, k);
    }
}

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

    heapSort (N);

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

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