#include <cstdlib>
#include <ctime>
#include <iostream>

using namespace std;

/**
   Zwraca indeks lewego dziecka
   @param index indeks węzła w kopcu
   @return indeks lewego dziecka danego węzła
*/
int get_left_child_index(int index)
{
   return 2 * index + 1;
}

/**
   Zwraca indeks prawego dziecka.
   @param index indeks węzła w kopcu
   @return indeks prawego dziecka danego węzła
*/
int get_right_child_index(int index)
{
   return 2 * index + 2;
}

/**
   Sprawia, by poddrzewo odpowiadało warunkowi kopca,
   o ile jego dzieci już go spełniają.
   @param a tablica do posortowania
   @param root_index indeks poddrzewa do naprawy
   @param last_index ostatni właściwy indeks drzewa
   zawierającego poddrzewo do naprawy
*/
void fix_heap(int a[], int root_index, int last_index)
{
   // Usuń korzeń.
   int root_value = a[root_index];

   // Podwyższaj poziom dzieci, dopóki są większe od korzenia.

   int index = root_index;
   bool done = false;
   while (!done)
   {
      int child_index = get_left_child_index(index);
      if (child_index <= last_index)
      {
         // Zamień dziecko na prawe, jeśli to jest większe.
         int right_child_index = get_right_child_index(index);
         if (right_child_index <= last_index
            && a[child_index] < a[right_child_index])
         {
            child_index = right_child_index;
         }
         
         if (root_value < a[child_index]) 
         {
            // Podwyższ poziom dziecka.
            a[index] = a[child_index];
            index = child_index;
         }
         else
         {
            // Wartość w korzeniu jest większa niż w obojgu dzieciach.
            done = true;
         }
      }
      else 
      {
         // Brak dzieci
         done = true; 
      }
   }
   
   // Zapisz wartość korzenia na wolnej pozycji.
   a[index] = root_value;
}

/**
   Porządkuje tablicę przy użyciu sortowania przez kopcowanie.
   @param a tablica do posortowania
   @param size liczba elementów tablicy a
*/
void heap_sort(int a[], int size)
{  
   int n = size - 1;
   for (int i = (n - 1) / 2; i >= 0; i--)
   {
      fix_heap(a, i, n);
   }
   while (n > 0)
   {
      // Zamień miejscami korzeń z ostatnim elementem.
      int temp = a[0];
      a[0] = a[n];
      a[n] = temp;
      n--;
      fix_heap(a, 0, n);
   }
}

/** 
   Wyświetla wszystkie elementy tablicy.
   @param a tablica do wyświetlenia
   @param size liczba elementów tablicy a
*/
void print(int a[], int size)
{  
   for (int i = 0; i < size; i++)
   {
      cout << a[i] << " ";
   }
   cout << endl;
}

int main()
{  
   srand(time(0));
   const int SIZE = 20;
   int values[SIZE];
   for (int i = 0; i < SIZE; i++)
   {
      values[i] = rand() % 100;
   }
   print(values, SIZE);
   heap_sort(values, SIZE);
   print(values, SIZE);
   return 0;
}

