heap.cc

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

#include "heap.h"
#include <iostream>
using namespace std;


leftistNode :: leftistNode(){
	//default construction function
}

leftistNode :: leftistNode(int x){
	//construction function with input element
	data = x;
	lChild = NULL;
	rChild = NULL;
    sPathLength = 1;
}

leftistNode :: ~leftistNode(){
	//deconstruction function
}

leftistTree :: leftistTree(){
	root = NULL;
}

leftistTree :: leftistTree(int x){
	leftistNode * rt =new leftistNode(x);
	root = rt;
}

leftistTree :: leftistTree(leftistNode* rt){
	//construction function from existing tree node
	root = rt;
}


leftistTree :: ~leftistTree(){
	//deconstruction function
}

leftistTree* leftistTree :: rightestTree(){
	//finding the tree rooting at its rightest child for melding
	//cut the tree off
	//return the sub-tree

	leftistNode* rightestNode = root; 
	leftistNode* secondRightest = root;

    int i=0;//record the level

	while (rightestNode->sPathLength>1){
		secondRightest =  rightestNode; //keep track of the parent of the righest child
		rightestNode = rightestNode -> rChild;
		
		i++;

	}
	if (rightestNode == root){// the root has no right child
		return this;
	}
	else {  //update the sPathLength value
			secondRightest->rChild = NULL; //cut the rightest-tree off
			secondRightest->sPathLength = 1;
			leftistNode* t = root;
            while (t!= secondRightest){
				t->sPathLength = t->sPathLength-1;
				t = t ->rChild;
				i--;
//				cout<<"level: "<<i<<" sPathLength: "<<t->sPathLength<<endl;
			}
		leftistTree* subTree = new leftistTree(rightestNode);
		return subTree;
	}	
}


void leftistTree :: swapChildren(){
	//swap left and right child of the root if s(left)<s(right)
	leftistNode* tmp = root->lChild;
	root->lChild = root->rChild;
	root->rChild = tmp;
}

leftistTree* leftistTree :: compareRoot(leftistTree* T){
	//compare the data of the root with that of another tree
	//return the root with smaller data
	if (root == NULL)//empty tree
		return T;
	else if (root->data > T->root->data)
		return T;
	else if (root->data < T->root->data)
		return this;
	else if (root->data == T->root->data)
		return this;
	else exit(-1);
}

leftistTree* leftistTree :: mergy (leftistTree* T){
	//mergy two trees, each has no right children
	leftistTree* newTree = new leftistTree(compareRoot(T)->root);//generate a new tree
	
	if (root == newTree->root) newTree->root->rChild = T->root;//mergy to root
	else if(T->root == newTree->root) newTree->root->rChild = root; //mergy to the other tree
//	else cout<<"error root!"<<endl; 
	if (newTree->root->lChild == NULL){
		newTree->root->lChild = newTree->root->rChild;
		newTree->root->rChild = NULL;
	}
	else if (newTree->root->lChild->sPathLength < newTree->root->rChild->sPathLength){
		newTree->swapChildren();
	}
    if (newTree->root->rChild == NULL){
		newTree->root->sPathLength = 1;
	}
	else newTree->root->sPathLength = newTree->root->rChild->sPathLength+1;
	return newTree;
}


leftistTree* leftistTree :: meld(leftistTree* T){
	//meld another tree with this tree
	//return the newTree
	if (root ==NULL)
		return T;
	else {
		leftistTree* mainTree = compareRoot(T);
		leftistTree* viceTree = (mainTree == this)? T:this;
		leftistTree* subTree = mainTree->rightestTree();
		if(subTree!=mainTree){
			subTree->meld(viceTree);
		}
		leftistTree* newTree = mainTree->mergy(viceTree);
		return newTree;
	}
}


leftistTree* leftistTree :: insert (int element){
	//insert a new node with input data
//	leftistNode* newNode = new leftistNode(element);
	leftistTree* newTree = new leftistTree(element);//construct a new tree for this data;
	root = meld(newTree)->root;
	return this;
}

leftistTree* leftistTree :: deleteMin(){
	//delete the minimum node(root)
	if (root == NULL){
//		cout<<"Sorry, the tree is already empty!"<<endl;
//		cout<<"What do you wanna delete?"<<endl;
		return this;
	}
	if (root->lChild == NULL){//with only one node
//		cout<<"The tree is empty!"<<endl;
		root = NULL;
		return this;
	}
	else if (root->rChild == NULL){//no right children
		root = root->lChild;
		return this;
	}
	else {
			leftistTree* mainTree = new leftistTree(root->lChild);
			leftistTree* viceTree = new leftistTree(root->rChild);
			root = mainTree->meld(viceTree)->root;
			return this;
	}
}

void leftistTree :: displayTree(){
	//display the tree in level order
	//using the dynamic arrary of leftistNode 
	leftistNode* p;
	leftistNode* q[SEQUENCE_MAX_SIZE];//dynamic arrary
	int front=0, rear=0;//head, tail of the array
	
	if(root!=NULL){
		rear = (rear+1)% SEQUENCE_MAX_SIZE;
		q[rear] = root;
	}//put the root into the array
    
	cout<<"The result leftist tree is:"<<endl;
	cout<<"[ ";
	while (front!=rear){//array is not empty
		front = (front+1) % SEQUENCE_MAX_SIZE;
		p=q[front];
		cout<<p->data<<" ";
		
		if (p->lChild!=NULL){
			rear = (rear+1) % SEQUENCE_MAX_SIZE;
			q[rear]=p->lChild;
		}
		if(p->rChild!=NULL){
			rear = (rear+1) % SEQUENCE_MAX_SIZE;
			q[rear]=p->rChild;
		}
	}
	cout<<"]"<<endl;
	if (root == NULL)
		cout<<"Attention : tree is empty!"<<endl;
	cout<<endl;
	
}

void leftistTree :: runRandomInsert(int* Array, int sequenceSize){
	//run the n insert operations according to the random input data array
	int* dataArray = Array;
	int i=0;
	while(i<sequenceSize){
		root = insert(*(dataArray+i))->root;
		i++;
	}
}



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

  **/
}

void leftistTree:: 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;
			root = deleteMin()->root;
			//displayTree();//check the operation
			//cout<<endl;
		}
        if(operType == 'I'){//insert
			in>>operNum;//read the operation Number
			//cout<<endl;
			//cout<<"***Operation: Insert number: "<<operNum<<"***"<<endl;
			root = insert(operNum)->root;
			//displayTree();//check the operation
			//cout<<endl;
		}
		if(operType == '*'){//stop sign
			cout<<"***Operations End***"<<endl;
		//	cout<<"***The final result tree is***"<<endl;
			displayTree();
			cout<<"***Thank You!***"<<endl;
			cout<<endl;
			return;
		}
	}
}

binoNode :: binoNode(){
	//default construction function
}

binoNode :: binoNode(int elem){
	//construct a bino node with input data
	data = elem;
	degree = 0;
	child = NULL;
	sibling = this;
}

binoNode :: ~binoNode(){
	//default deconstruction function
}


int binoNode:: getNodeDegree(){
	//return the degree of the node
	binoNode* p= child;
	if (p->sibling == child){//only one child
		degree = 1;
		return degree;
	}
	int i=1;
	while(p->sibling!=child){
		p=p->sibling;
		i++;
	}
	degree = i;
	return degree;
}



binoTree :: binoTree(){
	root =  NULL;
}

binoTree :: binoTree(int elem){
	//construction function with input data
	binoNode* newNode = new binoNode(elem);
	root = newNode;
}
binoTree :: binoTree(binoNode* rt){
	root = rt;
}

binoTree :: ~binoTree (){
	//default deconstruction function
}




binoHeap :: binoHeap(){
	binoNode* virtualNode = new binoNode(-1);
	virtualRoot = virtualNode;
	minElemPointer = NULL;
	for(int i=0; i<ROOT_MAX_DEGREE;i++){
		for(int j=0; j<TREE_MAX_NUM;j++){
			treeTable[i][j] = NULL;
		}
	}
}

binoHeap :: ~binoHeap(){
	//default deconstruction function
}

void binoHeap :: findMinPointer(){
	if (virtualRoot->child == NULL){//empty heap
//		cout<<"Attention: the heap is empty!"<<endl;
		return;
	}
	
	minElemPointer = virtualRoot->child;
	binoNode* rootPointer = virtualRoot->child;
	int number=0;
	
	while (rootPointer->sibling!= virtualRoot->child){
		if (rootPointer->sibling->data < minElemPointer->data){
			minElemPointer = rootPointer->sibling;
		}
		rootPointer = rootPointer ->sibling;
		number++;
	}
	if (rootPointer->sibling->data < minElemPointer->data){
		minElemPointer = rootPointer->sibling; 
	}
	number++;

//	cout<<"root number: "<<number + 1<<endl;// for checking the root numbers
}

		
void binoHeap :: merge(binoTree* formerTree, binoTree* latterTree){
	//merge the current two trees with the same root degree
	//update the tree table
	binoTree* mainTree;
	binoTree* viceTree;
	if ((formerTree->root == NULL)||(latterTree->root == NULL)){//empty tree
		cout<<"Wrong sub trees!"<<endl;
		exit(-1);
	}
	else if (formerTree->root->data > latterTree->root->data){
		mainTree = latterTree;
		viceTree = formerTree;
	}
	else if (formerTree->root->data <= latterTree->root->data){
		mainTree = formerTree;
		viceTree = latterTree;
	}
	else exit(-1);

	int originDegree = mainTree->root->degree;

//	cout<<"original degree: "<<originDegree<<endl;

	int i = mainTree->root->degree++;
	binoNode* p=mainTree->root->child;

	if (p==NULL){//main tree has no children
		mainTree->root->child = viceTree->root;
		p=viceTree->root;
	}

	while(i>1){
		p=p->sibling;
		i--;
	}// p points to the last sibling of the root`s child
/**	
	if (mainTree->root->child == p->sibling)
		cout<<"circuit!"<<endl;
	else cout<<"non-circuit!"<<endl;
  **/  //check whether the cricuit link is complete


	p->sibling = viceTree->root;
	viceTree->root->sibling = mainTree->root->child;

	/** update the tree table **/

	i=0;
	while(treeTable[originDegree][i]!=NULL){
		if((treeTable[originDegree][i]!=mainTree)&&(treeTable[originDegree][i]!=viceTree)){
			i++;//no matching for this two trees
		}
		else {//find these trees
				int j=i;
				if (treeTable[originDegree][j+1]==NULL){//this is the last tree
					treeTable[originDegree][j] = NULL;
					break;
				}
				while(treeTable[originDegree][j+1]!=NULL){//go round the left trees to move forward
				    treeTable[originDegree][j]=treeTable[originDegree][j+1];//move forward, delete this one selected
					treeTable[originDegree][j+1]=NULL;
					j++;
				}
		}