#include <vector>
#include <math.h>
using namespace std;
#ifndef HEAP_H
#define HEAP_H


template<class T>
class minHeap {
      
      
      
public:
void push(T);
T pop();
T top(){return Heap.front();};
minHeap()
    { size = 0;}
minHeap(T ar[],int sz)
    {
     size = 0;
     for (int i = 0 ; i < sz ; i++)
       push(ar[i]);
      buildminheap();
    }

void print(){
    for (int i = 0 ; i < size ; i++)
    cout<<Heap[i]<<endl;
    }

protected:
private:
vector<T> Heap; 
size_t size;
int giveleft(int  i) {  return  2*i + 1; }
int giveright(int  i) {  return  2*i + 2; }
void Heapsort();
void minHeapify(T);
size_t giveparent(size_t);
void buildminheap();
};	
template <class T>
void swap(vector<T> A, int i, int j)
{
  T temp = A[i];
  A[i] = A[j];
  A[j] = temp;
}

template<class T>
void minHeap<T>::buildminheap()
{
for (int i = (size/2)-1; i >=0 ; i --)
	minHeapify(i);
}
template <class T>
size_t minHeap<T>::giveparent(size_t index)
{

  return (size_t(floor((index-1) / 2)));
}
template<class T>
void minHeap<T>::minHeapify(T i)
{
T l = giveleft(i);
T r = giveright(i);
T largest;
if (l <=size-1 && Heap[l]<Heap[i])
       largest = l;
   else
       largest = i;
if (r <=size-1 && Heap[r]<Heap[largest])
   largest = r;
if (largest != i){
   T temp = Heap[i];
   Heap[i] = Heap[largest];
   Heap[largest] = temp;

   minHeapify(largest);
}
}
template<class T>
void minHeap<T>::push(T item)
{
Heap.push_back(item); 


for(size_t i=size; i>0 && (Heap[giveparent(i)] > Heap[i]); i = giveparent(i))
    swap(Heap[giveparent(i)], Heap[i]);
size++;

}


template<class T>
T minHeap<T>::pop()
{
T temp = Heap[0];
Heap[0] = Heap[size-1];
size--;
minHeapify(0);

return(temp);
}                      

template<class T>
void minHeap<T>::Heapsort()
{
buildminheap();
 for (int i = size-1; i >= 1; i--)
  {
    T temp = Heap[0];
    Heap[0] = Heap[i];
    Heap[i] = temp;
    minHeapify(i-1);
  }
}
 #endif