/*
 * BinaryHeap.cpp
 *
 *  Created on: 15 Eki 2011
 *      Author: Serdar KUZUCU
 */

#include <iostream>
#include <math.h>

using namespace std;

template<typename Comparable>
class BinaryHeap {
	public:
	explicit BinaryHeap( int capacity = 3 ) {
		objects = new Comparable[capacity+1];
		this->capacity = capacity;
		this->currentsize = 0;
	}

	void insert(const Comparable &o) {
		if(currentsize == capacity) {
			resize((capacity+1)*2);
		}
		int cell = ++currentsize;
		for(; cell>1 && objects[cell/2] > o; cell/=2)
			objects[cell] = objects[cell/2];
		objects[cell] = o;
	}

	void deleteMin() {
		objects[1] = objects[currentsize--];
		percolateDown(1);
	}

	void print() {
		int size = currentsize;
		int numsatir = 0;
		for(numsatir = 0; size>0; size-=pow(2,numsatir)+1, numsatir++);

		int citem = 1;
		for(int i=0; i<=numsatir; i++) {
			for(int k=numsatir-i; k>0; k--) {
				cout << " ";
			}

			for(int k=0; k<pow(2,i) && currentsize>=citem; k++) {
				cout << objects[citem++] << "  ";
			}
			cout << endl;
		}
		cout << endl;
	}

	bool empty() {
		return (currentsize==0);
	}

	private:
	int currentsize;
	int capacity;
	Comparable *objects;

	void resize(int newcapacity) {
		Comparable *newobjects = new Comparable[newcapacity];
		for(int i=0; i<=currentsize; i++) {
			newobjects[i] = objects[i];
		}
		delete(objects);
		this->objects = newobjects;
		capacity = newcapacity-1;
	}

	void percolateDown(int hole) {
		Comparable temp = objects[hole];
		int child;
		for( ; hole*2<=currentsize; hole = child ) {
			child = hole*2;
			if(child != currentsize && objects[child+1] < objects[child]) {
				child++;
			}
			if(objects[child] < temp) {
				objects[hole] = objects[child];
			} else {
				break;
			}
		}
		objects[hole] = temp;
	}
};