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