#include <fstream.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

/*
For a node with index = x in the array:
	its parent is (x-1)/2
	its lchild is 2*x+1
	its rchild is 2*x+2
*/

const int MAX_SIZE = 10;

typedef char string[100];
int heap[MAX_SIZE];
int curSize = 0;

void trickleUp(int index) {
	int parent = (index-1)/2;
	int newVal = heap[index];
	while (index > 0 && heap[parent] < newVal ) {
		heap[index] = heap[parent];
		index = parent;
		parent = (parent-1)/2;
	}
	heap[index] = newVal;
}

void trickleDown(int index) {
	int largerChild;
	int topVal = heap[index];
	while ( index<curSize/2 ) {
		int lChild = 2 * index + 1;
		int rChild = lChild + 1;
		if ( rChild<curSize && heap[lChild]<heap[rChild] )
			largerChild = rChild;
		else
			largerChild = lChild;
		if ( topVal >= heap[largerChild] )
			break;
		heap[index] = heap[largerChild];
		index = largerChild;
	}
}

bool insertNode(int i) {
	if ( curSize != MAX_SIZE ) {
		heap[curSize] = i;
		trickleUp(curSize++);
		return true;
	}
	return false;
}

int deleteNode() {
	if ( curSize != 0 ) {
		int root = heap[0];
		heap[0] = heap[--curSize];
		trickleDown(0);
		return root;
	}
	return NULL;
}

void initHeap() {
	for (int i=0; i<MAX_SIZE; i++) {
		heap[i] = 0;
	}
}

void main() {
	srand( (unsigned)time( NULL ) );
	ofstream outFile("heap.txt");
	int i;
	int d;
	int r = 0;
	initHeap();
	for (i=0; i<10; i++) {
		r = rand();
		if ( insertNode(r) ) {
			outFile << "A:" << r << "\n";
		}
	}
	for (i=0; i<10; i++) {
		outFile << "Iteration " << i << "\n";
		d = deleteNode();
		if ( d != NULL ) 
			outFile << "D:" << d << "\n";
		r = rand();
		if ( insertNode(r) )
			outFile << "A:" << r << "\n";
	}
}