#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;
// }
// }
// }