#include<iostream>
#include<cstdlib>
using namespace std;

typedef int itemtype;

struct Heap{
	void reheapdown(int root, int bottom);
	void reheapup(int root, int bottom);
	itemtype *elements;
	int size;
};

void Heap::reheapdown(int root, int bottom){
	int max_index;
	int right_index;
	int left_index;

	left_index = 2*root+1;
	right_index = 2*root+2;

	if(left_index <= bottom){
		if(left_index == bottom) max_index = left_index;
		else{
			if(elements[left_index] <= elements[right_index])
				max_index = right_index;
			else max_index = left_index;
		}
	
		if(elements[root] < elements[max_index]){
			swap(elements[root], elements[max_index]);
			reheapdown(max_index, bottom);
		}
	}
}


void Heap::reheapup(int root, int bottom){
	int parent;
	if(bottom > root){
		parent = (bottom-1)/2;
		if(elements[parent] < elements[bottom]){
			swap(elements[parent], elements[bottom]);
			reheapup(root, parent);
		}
	}

}

class PQ{
public:
	PQ();
	PQ(int);	//Constructor
	~PQ();		//Destructor
	PQ(const PQ& orig);	//Copy Constructor
	void operator = (PQ& rhs); // Overloaded = operator

	bool is_empty(){return cursize == 0;}
	bool is_full(){return cursize == maxsize;}
	void enqueue(itemtype newitem);
	void dequeue(itemtype& item);
	void display();
private:
	int cursize;
	int maxsize;
	Heap items;
	void copy(Heap source);
	void destroy();
};

PQ::PQ(){
	maxsize = 0;
	items.elements = new itemtype[maxsize];
	items.size=maxsize;
	cursize = 0;
}

PQ::PQ(int size){
	maxsize = size;
	items.elements = new itemtype[maxsize];
	items.size=maxsize;
	cursize = 0;
}

PQ::~PQ(){
	destroy();
	cout<<"Destructing\n";

}

void PQ::enqueue(itemtype newitem){
	if(! is_full()){
		items.elements[cursize] = newitem;
		items.reheapup(0,cursize);
		cursize++;
	}
	else cout<<"Op failed, Q full\n";
}

void PQ::dequeue(itemtype &item){
	if(!is_empty()){
		item = items.elements[0];
		items.elements[0] = items.elements[cursize-1];
		cursize--;
		items.reheapdown(0,cursize-1);
	}
}

PQ::PQ(const PQ& orig){
	copy(orig.items);
	cursize = orig.cursize;
	cout<<"Inside copy constructor\n";
}

void PQ::operator = (PQ& orig){
	if(this == &orig) return;
	else{
		destroy();
		copy(orig.items);
		cursize = orig.cursize;
	}
}

void PQ::copy(Heap source){
		maxsize = source.size;
		items.elements = new itemtype[maxsize];
		items.size=maxsize;
		for(int i=0;i<maxsize;++i){
			items.elements[i]=source.elements[i];
		}
	
}

void PQ::destroy(){
	maxsize=0;
	delete [] items.elements;
	items.size=0;
	cout<<"Inside destroy\n";
}


void PQ::display(){
	for(int i=0;i<cursize;++i)cout<<items.elements[i]<<endl;
}

int main(){
	const int size =20;
	itemtype x;
	PQ ob1(size);
	for(int i=1; i<=size; ++i){
		x=rand()%(3*size);
		ob1.enqueue(x);
	}
	cout<<endl<<endl;
	ob1.display();
	cout<<endl<<endl;

	PQ ob2 = ob1; //testing copy constructor
	PQ ob3;
	ob3 = ob1; //testing overloading of =

	ob1=ob1;
	for(i=1; i<=size; ++i){
		ob1.dequeue(x);
		cout<<x<<endl;
	}
	
	return 0;
}