maxbheapcpp.h

MaxHeap operation like insert and delete

#ifndef MAXBHEAPCPP_H
#define MAXBHEAPCPP_H

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

using namespace std;

template <class DType>
MaxBHeap<DType>::MaxBHeap(unsigned int size){

	maxkeys = size;
	Keys = new DType[maxkeys];
	numkeys = 0;
}

template <class DType>
MaxBHeap<DType>::MaxBHeap(const MaxBHeap<DType>& maxBHeap){
	maxkeys = maxBHeap.maxkeys;
	numkeys = maxBHeap.numkeys;
	Keys = new DType[maxkeys];
	for(unsigned int count =1; count <= maxBHeap; count++){
		Keys[count] = maxBHeap.Keys[count];
	}
}


template <class DType>
MaxBHeap<DType>& MaxBHeap<DType>::operator =(const MaxBHeap& maxBHeap){
	maxkeys = maxBHeap.maxkeys;
	numkeys = maxBHeap.numkeys;
	Keys = new DType[maxkeys];
	for(unsigned int count =1; count <= maxBHeap; count++){
		Keys[count] = maxBHeap.Keys[count];
	}
	return *this;
}

template <class DType>
MaxBHeap<DType>::~MaxBHeap(){

	delete [] Keys;

}


template <class DType>
void MaxBHeap<DType>::Build(DType *obj, unsigned int size){
	
	maxkeys = 100;
	numkeys = size;
	Keys = new DType[maxkeys];
	unsigned int count;
	for(count =1;count <=size; count++){
		Keys[count] = obj[count-1];
	}

	count = numkeys/2;
	
	while (count >= 1){
		percolatedown(count);
		count--;
	}
}

template <class DType>
void MaxBHeap<DType>::Insert(const DType& obj){
	Keys[++numkeys] = obj;
	DType temp;
	
	unsigned int i=numkeys;

	while( (i>1) && (Keys[i] > Keys[i/2])){
		temp = Keys[i];
		Keys[i] = Keys[i/2];
		Keys[i/2] = temp;
		i=i/2;
	}
}
template <class DType>
DType MaxBHeap<DType>::DeleteMax(){
	DType Max;


	if(IsEmpty())
		cout<<"Empty heap!"<<endl;
	
	else{
		Max = Keys[1];

		Keys[1] = Keys[numkeys];
		numkeys--;

		percolatedown(1);

	}
	return Max;
}

template <class DType>
void MaxBHeap<DType>::percolatedown(unsigned int pos){

	unsigned int left=2*pos;
	unsigned int right=2*pos+1;
	unsigned int largest = pos;

	DType temp;


	if ((left <= numkeys) && (Keys[left] > Keys[pos]))
		largest = left;

	if ((right <= numkeys) && (Keys[right] > Keys[largest]))
		largest = right;

	if(largest != pos)
	{
		temp = Keys[largest];
		Keys[largest]=Keys[pos];
		Keys[pos]=temp;
		
		percolatedown(largest);
	}
}

template <class DType>
bool MaxBHeap<DType>::IncKey(unsigned int pos, const DType& obj){
	DType temp;

	if(Keys[pos] > obj){
		cout << "new key is smaller than current keys";
		return false;
	}

	else{

		Keys[pos]=obj;
		unsigned int i = pos;
		while ( (i>1) && (Keys[i] > Keys[i/2])){
			temp = Keys[i];
			Keys[i] = Keys[i/2];
			Keys[i/2] = temp;
			i=i/2;
		}

		return true;
	}
}

template <class DType>
bool MaxBHeap<DType>::DecKey(unsigned int pos, const DType &obj){
	//DType temp;

	if(Keys[pos] < obj){
		cout << "new key is larger than current keys";
		return false;
	}
	else{
		Keys[pos] = obj;

		percolatedown(pos);
		
		return true;

	}

}


template <class DType>
bool MaxBHeap<DType>::IsEmpty(){

	return (numkeys < 1);
	
}

template <class DType>
bool MaxBHeap<DType>::IsFull(){

	
	return (numkeys >= maxkeys);
}

template <class DType>
ostream& operator << (ostream &os, const MaxBHeap<DType>& maxBHeap) {
	
	for(unsigned int i=1; i<=maxBHeap.numkeys;i++){
		cout << setw(5) << maxBHeap.Keys[i];
	}
	cout << endl;
	
	//unsigned int level =0;
	int level=0;
	int count =1;
	//unsigned int count =1;

	while(count <= maxBHeap.numkeys){
		level++;
		count = count * 2;

	}
	unsigned int j=1;

	for(count=1;count<=level;count++){
		for(unsigned int i=0;i<pow(2.0,count-1);i++)
		{
			for(unsigned int l=0;l< 3*pow(2.0,level-count); l++){
				cout <<" ";
			}
			if(j<=maxBHeap.numkeys){
				if(j/2==0){
					cout << setw(2) << maxBHeap.Keys[j];
					j++;
				}
				else{
					if(j%2==0){
						cout << "/"<< setw(2) <<maxBHeap.Keys[j];
						for(unsigned int y=0; y < (3*pow(2.0,level-count))-3;y++)
						cout << " ";
						j++;
					}
					else{
						cout << maxBHeap.Keys[j] << "\\";
						for(unsigned int y=0; y < (3*pow(2.0,level-count))-3;y++)
						cout << " ";
						j++;
					}
				
				}
			}
			
		}

		cout << endl;


	}
	

	return os;
}



#endif