#include<iostream>
#include<cmath>
#include<random>
#include<graphviz/cgraph.h>
#include<graphviz/gvc.h>
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;
	}
	~Heap(){
		free(heap_memory);
	}
	void make_image_recur(Agraph_t *g, Agnode_t *parent, size_t place){
		char number[32];
		sprintf(number, "%d\n(%lu)", heap_memory[place], place);
		Agnode_t *us = agnode(g, number, 1);
		if(parent)
			Agedge_t *e = agedge(g, parent, us, (char*)"", 1);
		size_t lchild = place * 2 + 1;
		size_t rchild = lchild + 1;
		if(lchild < end)
			make_image_recur(g, us, lchild);
		if(rchild < end)
			make_image_recur(g, us, rchild);
	}

	void make_image(string name){
		Agraph_t *g;
		g = agopen((char*)"G", Agdirected, 0);
		Agsym_t *color_attr = agattr(g, AGNODE, (char*)"color", (char*)"black");

		// Go through the tree, and add all our nodes!
		// Add our own node
		// If there is a left subtree, add the left subtree
		// If there is a right subtree, add the right subtree
		make_image_recur(g, 0, 0);

		GVC_t* gvc = gvContext();
		gvLayout(gvc, g, "dot");
		agwrite(g, stdout);	;
		gvRenderFilename(gvc, g, "png", (name + ".png").c_str());
		gvFreeLayout(gvc, g);
		agclose(g);
	}
};

int main(){
	Heap test_heap;
	srandom((long unsigned int)&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() < 50)
		test_heap.insert(random() % 1000);
	test_heap.make_image("heap");
	while(test_heap.size())
		cout << test_heap.pop() << endl;
	return 0;
}