heap.h

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

#ifndef HEAP_H
#define HEAP_H

#include<iostream>
#include<stdlib.h>
#include<time.h>
#include<sstream>
#include<string.h>
#include<string>
#include<fstream>


using namespace std;

#define SEQUENCE_MAX_SIZE 5000
//#define STRING_MAX_SIZE 20000
#define TREE_MAX_NUM 500
#define ROOT_MAX_DEGREE 100

class leftistNode;
class leftistTree;

class binoNode;
class binoTree;
class binoHeap;

int* randomInput(int);//generate the random input data array
void randomCompare();
//compare the unit opration time of two heaps in random mode


class leftistNode{
public:
	int data;
	leftistNode*  lChild;
	leftistNode*  rChild;
	int sPathLength;
    
	leftistNode();
	leftistNode(int);
    ~leftistNode();
};


class leftistTree{
public:
	leftistNode* root;
	
	leftistTree();
	leftistTree(int);
	leftistTree(leftistNode*);
	~leftistTree();
    
    leftistTree* rightestTree();
	//finding the tree rooting at its rightest child for melding
	
	void swapChildren ();
	//swap left and right child of the root if s(left)<s(right)
    
	leftistTree* compareRoot(leftistTree*);
	//compare the data of the root with that of another tree
	//return the tree with smaller root data

	leftistTree* mergy (leftistTree*);
	//mergy two trees, each has no right children
	//return the newTree

	leftistTree* meld(leftistTree*);
	//meld another tree with this tree
	//return the new tree

	leftistTree* insert (int);
	//insert a new node with input data
	
	leftistTree* deleteMin();
	//delete the minimum node(root)

	void displayTree();
	//display the tree

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

	void runRandomInput(int);
	//parameter int: number of the sequence data
	//run the operations according to random Input
	//output the result leftist tree

	void runFileInput(string);
	//parameter string: directory of the file
	//run the operations according to file input 
	//output the result leftist tree
};




class binoNode{
public:
	int data;
	int degree;//number of children
	binoNode* child;//pointer to one of its children
	binoNode* sibling;//sibling node

	binoNode();
	binoNode(int);
	~binoNode();

	int getNodeDegree();//return the degree of the node
};

class binoTree{
public:
	binoNode* root; //root of tree

	binoTree();
	binoTree(int);
	binoTree(binoNode*);
	~binoTree();
};

class binoHeap{
public:
	binoNode* virtualRoot;// create a virtual root, all roots of trees as its children
	binoNode* minElemPointer;//pointer to the minimum root of all roots
	binoTree* treeTable[ROOT_MAX_DEGREE][TREE_MAX_NUM];//tree table used for pairwise

	binoHeap();
	~binoHeap();
	void findMinPointer();
	//find the minimum root
	
	 void merge(binoTree*, binoTree*);
	//merge the current two trees with the same root degree
	//update the tree table

	void pairwise();
	//pairwise the current trees using tree table

	binoHeap* insert(int);
	//insert node with given data

	binoHeap* reInsert(binoNode*);
	//reinsert a series of bino trees sibling to the parameter bino tree

	binoHeap* deleteMin();
	//delete the minimum node;

	void displayHeap();
	//display the heap

	void runRandomInsert(int* Array, int sequenceSize);
		//run the insert operations according to the random input data array 
	
	void 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")
	//output the result heap

	void runFileInput(string directory);
	//parameter string: directory of the file
	//run the operations according to file input 
	//output the result leftist tree


};

#endif