#ifndef MAXHEAP_H
#define MAXHEAP_H

#include <vector>

using namespace std;

/**
   Klasa ta stanowi implementację kopca.
*/
template<typename T>
class MaxHeap
{
public:
   /**
      Konstruuje pusty kopiec.
   */
   MaxHeap();

   /**
      Dodaje do kopca nowy element.
      @param element dodawany element
   */
   void push(T element);

   /**
      Pobiera największy element przechowywany w kopcu.
      @return największy element
   */
   T top() const;

   /**
      Usuwa z kopca największy element.
   */
   void pop();

   /**
      Pobiera rozmiar kopca.
      @return rozmiar
   */
   int size() const;
private:
   /**
      Zamienia drzewo z powrotem w kopiec, pod warunkiem że warunek kopca
      jest naruszony tylko w korzeniu.
   */
   void fix_heap();

   /**
      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) const;

   /**
      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) const;

   /**
      Zwraca indeks rodzica.
      @param index indeks węzła w kopcu
      @return indeks rodzica danego węzła
   */
   int get_parent_index(int index) const;

   /**
      Zwraca wartość lewego dziecka.
      @param index indeks węzła w kopcu
      @return wartość lewego dziecka danego węzła
   */
   T get_left_child(int index) const;

   /**
      Zwraca wartość prawego dziecka.
      @param index indeks węzła w kopcu
      @return wartość prawego dziecka danego węzła
   */
   T get_right_child(int index) const;

   /**
      Zwraca wartość rodzica.
      @param index indeks węzła w kopcu
      @return wartość rodzica danego węzła
   */
   T get_parent(int index) const;
   
   vector<T> elements;   
};

template<typename T>
MaxHeap<T>::MaxHeap()
{
   T dummy;
   elements.push_back(dummy); 
}

template<typename T>
void MaxHeap<T>::push(T new_element)
{
   // Dodaj nowy liść.
   T dummy;
   elements.push_back(dummy);
   int index = elements.size() - 1;
      
   // Obniż poziom rodziców mniejszych niż nowy element.
   while (index > 1 && get_parent(index) < new_element) 
   {
      elements[index] = get_parent(index);
      index = get_parent_index(index);
   }

   // Zapisz nowy element na wolnej pozycji.
   elements[index] = new_element;
}

template<typename T>
T MaxHeap<T>::top() const
{
   return elements[1];
}

template<typename T>
void MaxHeap<T>::pop()
{
   // Usuń ostatni element.
   int last_index = elements.size() - 1;
   T last = elements[last_index];
   elements.pop_back();
   if (last_index > 1)
   {
      elements[1] = last;
      fix_heap();     
   }
}

template<typename T>
void MaxHeap<T>::fix_heap()
{
   T root = elements[1];
   
   int last_index = elements.size() - 1;
   // Podwyższ poziom dzieci usuniętego korzenia, dopóki są większe niż korzeń.
   int index = 1;
   bool done = false;
   while (!done)
   {
      int child_index = get_left_child_index(index);
      if (child_index <= last_index)
      {
         // Weź większe dziecko.
         
         // Weź najpierw lewe dziecko.
         T child = get_left_child(index);
         
         // Zamień je na prawe, jeśli to jest większe.
         if (get_right_child_index(index) <= last_index 
            && child < get_right_child(index))
         {
            child_index = get_right_child_index(index);
            child = get_right_child(index);
         }
         
         // Sprawdź, czy większe dziecko jest większe niż korzeń.
         if (root < child) 
         {
            // Podwyższ poziom dziecka.
            elements[index] = child;
            index = child_index;
         }
         else
         {
            // Korzeń jest większy niż oboje dzieci.
            done = true;
         }
      }
      else 
      {
         // Brak dzieci
         done = true; 
      }
   }
   
   // Zapisz element z korzenia na wolnej pozycji.
   elements[index] = root;
}

template<typename T>
int MaxHeap<T>::size() const
{
   return elements.size() - 1;
}

template<typename T>
int MaxHeap<T>::get_left_child_index(int index) const
{
   return 2 * index;
}

template<typename T>
int MaxHeap<T>::get_right_child_index(int index) const
{
   return 2 * index + 1;
}

template<typename T>
int MaxHeap<T>::get_parent_index(int index) const
{
   return index / 2;
}

template<typename T>
T MaxHeap<T>::get_left_child(int index) const
{
   return elements[2 * index];
}

template<typename T>
T MaxHeap<T>::get_right_child(int index) const
{
   return elements[2 * index + 1];
}

template<typename T>
T MaxHeap<T>::get_parent(int index) const
{
   return elements[index / 2];
}

#endif

