heap.cc

This code implements min binomial heaps and min leftist trees.Plus, measure and compare the relative

	}

	i=0;
	while(treeTable[originDegree+1][i]!=NULL){ 
		i++; 
	}//find the last one

	treeTable[originDegree+1][i]=mainTree;
}

void binoHeap :: pairwise(){
	//pairwise the current trees using tree table

	int rootDegree = 0;//indicate the degree of root
	binoTree* head;
	// head is to be served as the sibling of the largest degree tree
	binoTree* prior;
	//prior is to be served as the tree with smaller degree, used as the prior of the next tree
	for(;rootDegree<ROOT_MAX_DEGREE;rootDegree++){
		while(treeTable[rootDegree][1]!=NULL){//at most one tree for each degree. otherwise merge
			merge(treeTable[rootDegree][0],treeTable[rootDegree][1]);//merge the first and second tree, afterwards, new first and second trees moved forward
																	// the only one tree of each degree is treeTable[rootDegree][0]
		}
	}
	
	rootDegree = 0;
	while((rootDegree<ROOT_MAX_DEGREE)&&(treeTable[rootDegree][0]==NULL)){
		rootDegree++;
	}// look for the first degree having a tree

	if (rootDegree == ROOT_MAX_DEGREE){// no trees
		cout<<"There are no trees at all!"<<endl;
		return;
	}
	else 
	{
		head = treeTable[rootDegree][0];
		prior = head;
		rootDegree++;
	}

	while(rootDegree<ROOT_MAX_DEGREE){
		if (treeTable[rootDegree][0]!=NULL){//next degree having tree
			prior->root->sibling = treeTable[rootDegree][0]->root;
			prior = treeTable[rootDegree][0];
		}
		rootDegree++;
	}


	prior->root->sibling = head->root;//tail(largest degree) root next to the 0 degree node

	virtualRoot->child = prior->root; //prior->root is the one cannot be empty

	findMinPointer();//find the minimum pointer

	virtualRoot->child = minElemPointer;

//	cout<<"Min Pointer: "<<minElemPointer->data<<endl;

}


binoHeap* binoHeap :: insert(int elem){
	//insert node with given data
	binoTree* newTree = new binoTree(elem);
	if (treeTable[0][0] == NULL){//no one-degree node
		treeTable[0][0] = newTree;
	}
	else treeTable[0][1] = newTree;
	pairwise();
	return this;
}

binoHeap* binoHeap :: reInsert(binoNode* firstChild){
	//reinsert a series of bino trees sibling to the parameter bino tree
	if (firstChild==NULL){//
//		cout<<"no children"<<endl;
	}
	binoNode* pNode = firstChild;
	binoTree* pTree = new binoTree(pNode);
	while(pNode->sibling!=firstChild){
		if (treeTable[pNode->degree][0] == NULL){
			treeTable[pNode->degree][0] = pTree;
		}
		else treeTable[pNode->degree][1]= pTree;
		pTree = new binoTree(pNode->sibling);// reconstructe all next trees because they link to the firstChild only on the root, not the tree themselves
		pNode = pNode->sibling;
	}
	if (treeTable[pNode->degree][0] == NULL){
		treeTable[pNode->degree][0] = pTree;
	}
	else treeTable[pNode->degree][1]= pTree;

	pairwise();
	return this;
}


binoHeap* binoHeap :: deleteMin(){
	//delete the min node
	binoNode* pNode = minElemPointer;
	if (pNode == NULL ){
		//cout<<"Sorry, the heap is Empty!"<<endl;
		//cout<<"What do you wanna delete?"<<endl;
//		cout<<endl;
	}

	else if (pNode->sibling == pNode){//only one tree
	   //minElemPointer = pNode->child;
	  //	virtualRoot->child = pNode->child;
		if (pNode->child==NULL){
		//	cout<<"Attention: the heap is empty!"<<endl;
			treeTable[pNode->degree][0]=NULL;
			virtualRoot->child = NULL;
	        minElemPointer = NULL;
			return this;
		}
		treeTable[minElemPointer->degree][0]=NULL;
		reInsert(pNode->child);
	}
   
	else if (pNode->child==NULL){//only its sibling, no children

		//minElemPointer = pNode->sibling;
		//virtualRoot->child = pNode->sibling;
		while(pNode->sibling!=minElemPointer){//find the prior to min element pointer
			pNode = pNode->sibling;
		}
		pNode->sibling = minElemPointer ->sibling;
		virtualRoot->child = pNode->sibling;
		treeTable[minElemPointer->degree][0]=NULL;//update the tree table
		minElemPointer = pNode->sibling;
	}
	else{
		while(pNode->sibling!=minElemPointer){//find the prior to min element pointer
			pNode = pNode->sibling;
		}
		pNode->sibling = minElemPointer ->sibling;
		virtualRoot->child = pNode->sibling;
		treeTable[minElemPointer->degree][0]=NULL;//update the tree table
		reInsert (minElemPointer->child);
	}
	return this;
}


void binoHeap :: displayHeap(){
	//display the heap in level order
	//using the dynamic arrary of binoNode and circuit link 
	
	binoNode* p;
	binoNode* nextNode;
	binoNode* q[SEQUENCE_MAX_SIZE];//dynamic array
	int front=0, rear=0;//head, tail of the array
	int level[10]={0};// refers to number of nodes in each level
	if(virtualRoot!=NULL){
		rear = (rear+1)% SEQUENCE_MAX_SIZE;
		q[rear] = virtualRoot;
		level[0]=1;
	}//put the root into the array
    
	cout<<"The result binomial heap is:"<<endl;
	if (virtualRoot->child==NULL){
		cout<<"[ ]"<<endl;
		cout<<"Attention: The heap is empty!"<<endl;
		return;
	}
	else
	{
		int i=0, k=1;
		while(front!=rear&&i<10){
			while (k<=level[i]){
				front = (front+1) % SEQUENCE_MAX_SIZE;
				p=q[front];
				k++;
				nextNode = p->child;
				if (nextNode!=NULL){
					if (nextNode->sibling == p->child){//only one child
						rear = (rear+1) % SEQUENCE_MAX_SIZE;
						q[rear]=nextNode;
						level[i+1]++;
					}
					else
					{	
						level[i+1]=level[i+1]+p->getNodeDegree();
						while(nextNode->sibling!=p->child){
							rear = (rear+1) % SEQUENCE_MAX_SIZE;
							q[rear]=nextNode;
							nextNode = nextNode->sibling;
						}
						rear = (rear+1) % SEQUENCE_MAX_SIZE;
						q[rear]=nextNode;
//						levelPoint[i]=(rear+1)% SEQUENCE_MAX_SIZE;
//						i++;
					}
				}
				if (p == virtualRoot) {
					/**
					cout<<"Level 0: [";
					cout<<p->data<<" ";
					cout<<"]"<<endl;
					**/
					continue;
				}
			
			else{ 
					cout<<p->data<<" ";
				}
		
			}
			k=1;
			if (p!=virtualRoot)	cout<<"]"<<endl;

			if (level[i+1]>0){
				cout<<"Level "<<++i<<": [";
			}
			else if (level[i+1]==0){
				return;
			}
			else {
				cout<<"level information wrong!"<<endl;
				return;
			}	
		}

/**
		if (p == virtualRoot) continue;
		else{ 
			for(int j=1; j<i;j++){
				if(front==levelPoint[j]){
					cout<<"level"<<levelPoint[j]<<": ";
					cout<<p->data<<" ";
					break;
				}
			}
			cout<<p->data<<" ";
		}
	}
**/
		if (minElemPointer == NULL)
			cout<<"Attention : tree is empty!"<<endl;
		cout<<endl;
	}
}

void binoHeap :: runRandomInsert(int* Array, int sequenceSize){
	//run the insert operations according to the random input data array 

	int* dataArray = Array;
	
	/*
	cout<<endl;
	cout<<"input dataArray:"<<endl;
	for(int k=0; k<sequenceSize;k++){
		cout<<*(dataArray+k);
	}
	*/

	int i=0;
	while(i<sequenceSize){
		//	cout<<endl;
		//	cout<<"***Operation: Insert number: "<<*(dataArray+i)<<"***"<<endl;
		    insert(*(dataArray+i));
		//	displayHeap();//check the operation
		//	cout<<endl;
			i++;
	}
	/**
	cout<<endl;
	cout<<"***Operations End: ***"<<endl;
	cout<<"***The final heap is: ***"<<endl;
	displayHeap();
	cout<<"***Thank You!***"<<endl;
	cout<<endl;
	**/
}

void binoHeap :: runRandomInput(int sequenceSize){
	//run the operations according to the random input data array and operation type
	//use random(2) to generate the opration type 0(insert--"I") 1(deleteMin--- "D")

	int* dataArray = randomInput(sequenceSize);
	
	/*
	cout<<endl;
	cout<<"input dataArray:"<<endl;
	for(int k=0; k<sequenceSize;k++){
		cout<<*(dataArray+k);
	}
	*/

	int i=0;
	while(i<sequenceSize){
		//cout<< i <<endl;
		//confirm the operation type for each operating data
		int type = (int)(2/(float)RAND_MAX * rand());
		//cout<<type<<endl;
		if (type == 1){//deleteMin
		//	cout<<endl;
		//	cout<<"***Operation"<<i<<: Delete Min***"<<endl;
			deleteMin();
			//root = deleteMin()->root;
			//displayHeap();//check the operation
		//	cout<<endl;
			i++;
		}
		else if (type == 0){
		//	cout<<endl;
		//	cout<<"***Operation "<<i<<: Insert number: "<<*(dataArray+i)<<"***"<<endl;
		    insert(*(dataArray+i));
		//	displayHeap();//check the operation
		//	cout<<endl;
		//	i++;
		}
	}
	/**
	cout<<endl;
	cout<<"***Operations End: ***"<<endl;
	cout<<"***The final heap is: ***"<<endl;
	displayHeap();
	cout<<"***Thank You!***"<<endl;
	cout<<endl;
	**/
}

void binoHeap :: runFileInput(string directory){
	//run the operations according to the input file with the given directory
	
	char operType;
	int operNum;
	ifstream in;
	in.open(directory.c_str());//read the file
	if(!in){
		cout<<"Cannot open the input file!"<<endl;
		exit(-1);
	}
	while(in){
		in>>operType;
		if (operType == 'D'){//deleteMin
		//	cout<<endl;
		//	cout<<"***Operation: Delete Min***"<<endl;
			deleteMin();
		//	displayHeap();//check the operation
		//	cout<<endl;
		}
        if(operType == 'I'){//insert
			in>>operNum;//read the operation Number
		//	cout<<endl;
		//	cout<<"***Operation: Insert number: "<<operNum<<"***"<<endl;
			insert(operNum);
		//	displayHeap();//check the operation
		//	cout<<endl;
		}
		if(operType == '*'){//stop sign
		//	cout<<endl;
			cout<<"***Operations End***"<<endl;
		//	cout<<"***The final result heap is***"<<endl;
			displayHeap();
			cout<<"***Thank You!***"<<endl;
			return;
		}
	}
}



int* randomInput(int sequenceSize){
	//generate the test sequence according to the sequenceSize
	//use random(seqenceSize) to getnerate the oprating data
	//return the int array of input

	static int dataArray[SEQUENCE_MAX_SIZE];//only include the number
	
	for(int i=0; i<sequenceSize; i++){
		dataArray[i] = i; //init the dataArray
	}

	for(int i=0; i<sequenceSize; i++){
		int tmp = 0;
		tmp = dataArray[i];
		int latter = i + (int)((sequenceSize-1-i)/(float)RAND_MAX * rand()); // order of the exchange element 
		//cout<<endl;
		//cout<<i<<" "<<latter<<endl;
		dataArray[i] = dataArray[latter];
		dataArray[latter] = tmp;
	}
	return dataArray;
}

void randomCompare(){
	//compare the unit opration time of two heap sorts in random mode
	leftistTree* myTree = new leftistTree();
	binoHeap* myHeap = new binoHeap();

	int n[7]={100,500,1000,2000,3000,4000,5000};
	int	m=5000;
	clock_t Start, Time;

	for(int i=0; i<=6; i++){
		cout<<"*** n="<<n[i]<<",";
		cout<<" m="<<m<<"***"<<endl;
		int* randomList = randomInput(10);//create a random list of n elements

		myHeap->runRandomInsert(randomList,n[i]);//insert the n elements to initial the binomial heap

		myTree->runRandomInsert(randomList,n[i]);//insert the n elements to initial the leftist tree

		
		Start = clock();
		for(int j=0;j<5;j++){//iteration 5 times to get average
			myHeap->runRandomInput(m);
		}

		Time = clock()-Start;
		Time = Time/(5*m/1000);
		cout<<"each binomial heap operation needs time(MUs): "<<Time<<endl;

		Start = clock();
		for(int j=0;j<5;j++){
			myTree->runRandomInput(m);
		}
		Time = clock()-Start;
		Time = Time/(5*m/1000);
		cout<<"each leftist tree operation needs time(MUs): "<<Time<<endl;
		cout<<endl;
		cout<<endl;
	}
}



			
int main(int argc, char* argv[]){
	if(strcmp(argv[1],"-r")==0){
		randomCompare();
		return 1;	
	}
	else if(strcmp(argv[1],"-il")==0){
		leftistTree* myTree = new leftistTree();
		myTree->runFileInput(argv[2]);
		return 0;
	}
	else if (strcmp(argv[1],"-ib")==0){
		binoHeap* myHeap = new binoHeap();
		myHeap->runFileInput(argv[2]);
		return 1;
	}
	else 
	{
		cout<<"Invalid Parameter!"<<endl;
		return 0;
	}
	
}