#include <vector>

void maxHeapify(std::vector<int> &heap, int index);

int pop(std::vector<int> &heap) {

    if (heap.empty())

        return -1; 

 

    int max_element = heap[0];

    heap[0] = heap.back(); 

    heap.pop_back(); 

    maxHeapify(heap, 0); 

 

    return max_element;

}

 

void maxHeapify(std::vector<int> &heap, int index) {

    int left = 2 * index + 1;

    int right = 2 * index + 2;

    int largest = index; 

 

    if (left < heap.size() && heap[left] > heap[largest])

        largest = left;

 

    

    if (right < heap.size() && heap[right] > heap[largest])

        largest = right;

 

   

    if (largest != index) {

        std::swap(heap[index], heap[largest]);

        maxHeapify(heap, largest);

    }

}

 

// Code Snippet of the push function: 

//

//     void push(vector<int> &heap, int x)

//     {

//           heap.push_back(x);

//

//            // Posistion of the current inserted element.

//            int pos=heap.size()-1;

//

//            // Shifting the element up until it reaches the top most node if it is larger than its parent.

//            while(pos>0)

//            {

//                int parent = (pos-1)/2;

//                if(heap[pos] > heap[parent])

//                {

//                    swap(heap[parent],heap[pos]);

//                    pos=parent;

//               }

//              else

//              {

//                  // As parent is larger the element now is in its correct position. 

//                  break;

//              }

//          }

//      }