#include<iostream>
#include<cmath>
#include<random>
using namespace std;

class Heap {
	int *heap_memory;
	size_t end = 0;
	size_t allocation = 100;
	public:
	Heap() {
		heap_memory = (int*)malloc(sizeof(int) * 100);
	}
	void insert(int new_number){
		if(end >= allocation){
			allocation *= 2;
			heap_memory = (int*)realloc(heap_memory, allocation * sizeof(int));
		}
		heap_memory[end++] = new_number;
		reorder_up(end - 1);
//		print_heap_as_array();
	}
	void reorder_up(size_t idx){
//		cout << "reorder_up:  ";
//		print_heap_as_array();
		if(!idx)
			return;
		size_t parent_idx = (idx-1)/2;
		if(heap_memory[parent_idx] >= heap_memory[idx])
			return;
		int tmp = heap_memory[parent_idx];
		heap_memory[parent_idx] = heap_memory[idx];
		heap_memory[idx] = tmp;
		reorder_up(parent_idx);
	}
	void reorder_down(size_t idx){
//		cout << "reorder_up:  ";
//		print_heap_as_array();
		size_t lchild = idx * 2 + 1;
		size_t rchild = lchild + 1;
		if(rchild >= end){
			heap_memory[idx] = heap_memory[end - 1];
			reorder_up(idx);
			return;
		}
		size_t schild = rchild;
		if(heap_memory[lchild] > heap_memory[rchild])
			schild = lchild;
		heap_memory[idx] = heap_memory[schild];
		reorder_down(schild);
	}
	int get_max(){
		if(end)
			return heap_memory[0];
	}
	int pop(){
		int retval = heap_memory[0];
		reorder_down(0);
		end--;
		return retval;
	}
	size_t size(){
		return end;
	}
	void print_heap_as_array(){
		for(int i = 0; i < end; i++)
			cout << heap_memory[i] << " ";
		cout << endl;
	o
	~Heap(){
		free(heap_memory);
	}
};

int main(){
	Heap test_heap;
	test_heap.insert(4);
	test_heap.insert(12);
	test_heap.insert(1);
	test_heap.insert(6);
	test_heap.insert(7);
	test_heap.insert(800);
	while(test_heap.size())
		cout << test_heap.pop() << endl;
//	while(test_heap.size() < 300)
//		test_heap.insert(random() % 1000);
//	while(test_heap.size())
//		cout << test_heap.pop() << endl;

	return 0;
}