#include <algorithm>
#include <limits>
#include "heap.h"
 
int heapSize;
 
//Восстановление свойства кучи
void heapify(int a[], int i){
    int left = 2*i;
    int right = 2*i + 1;
    //heapSize - количество элементов в куче
    int largest = i;
    if((left <= heapSize) && (a[left] > a[i]))
        largest = left;
    if((right <= heapSize) && (a[right] > a[largest]))
        largest = right;
    if(largest != i){
        std::swap(a[i], a[largest]);
        heapify(a, largest);
    }
}
 
//перестроение в кучу массива длина size
void buildHeap(int a[], int size){
    heapSize = size;
    for(int i = size/2; i >= 0; i--)
        heapify(a, i);
}
 
//Изменение значения элемента
void heapIncreaseKey(int a[], int i, int key){
    if(key < a[i])
        return; //Ошибка
    a[i] = key;
    while((i > 0) && (a[i/2] < a[i])){
        std::swap(a[i], a[i/2]);
        i = i / 2;
    }
}
 
//Добавление элемента
void heapInsert(int a[], int key){
    heapSize = heapSize + 1;
    a[heapSize] = -INT_MAX;
    heapIncreaseKey(a, heapSize, key);
}
 
//Извлечение максимального элемента
int heapExtractMax(int a[]){
    if(heapSize < 0)
        return 0;   //Ошибка: куча пуста
    int max = a[0];
    a[0] = a[heapSize];
    heapSize = heapSize - 1;
    heapify(a, 0);
    return max;
}