#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

using namespace std;

int main()
{
    const int N = 5;  // liczebność zbioru
    int d[N + 1], i, j, k, m, x; //d[ ]     - Zbiór zawierający elementy do wstawienia do kopca. Numeracja elementów rozpoczyna się od 1.
    /*i - zmienna licznikowa pętli umieszczającej kolejne elementy zbioru w kopcu, i nldo. N, i nldo.{ 2,3,...,n }
        j, k - indeksy elementów leżących na ścieżce od wstawianego elementu do korzenia, j, k nldo. C
        x - zmienna pomocnicza przechowująca tymczasowo element wstawiany do kopca*/
    srand((unsigned)time(NULL));

    for (i = 1; i <= N; i++)
    {
        d[i] = rand() % 100; cout << setw(4) << d[i];
    }
    cout << endl;

    // Budujemy kopiec

    for (i = 2; i <= N; i++) // zaczynamy od 2 bo 1 i tak zostanie na swoim miejscu
    {
        j = i; k = j / 2; //wskaźnik na poprzedni indeks i z tego porównujemy wartości
        x = d[i]; // zapamietuje wskazany element
        while ((k > 0) && (d[k] < x)) // dopoki k nie rowna sie 0 albo przodek nie jest wiekszy od x
        {
            d[j] = d[k];
            j = k; k = j / 2;
        }
        d[j] = x;
    }

     /*Rozbieramy kopiec*/

    for (i = N; i > 1; i--)
    {
        swap(d[1], d[i]); // zamiana korzenia z ostatnią wartością
        j = 1; k = 2; //j - indeks przodka, k - indeks lewego potomka, petla konczy sie gdy j nie posiada potomkow
        while (k < i) // wykonuje się, dopóki nie dojdziemy do końca zbioru
        {
            if ((k + 1 < i) && (d[k + 1] > d[k])) //sprawdzenie warunku kopca
                m = k + 1;
            else
                m = k;
            if (d[m] <= d[j]) break; // sprawdzenie warunku kopca
            swap(d[j], d[m]);//brak zachowania warunku kopca, zamieniamy przodek z największym potomkiem
            j = m; k = j + j; // przyjmujemy za m wezel nadrzedny, wyznaczamy indeks lewego potomka w k i kontynuujemy petle
        }
    }

    cout << "Po sortowaniu:\n\n";
    for (i = 1; i <= N; i++) cout << setw(4) << d[i];
    cout << endl;
    system("PAUSE");
    return 0;
}