pheap.cpp

I implement Dijkstra s Single Source Shortest Path, say SSP, algorithm for directed graphs using a s

#include "PHeap.h"

/*
 *Constructor, Initialize the array to store the medium state
 *during the Dijkstra.
 *int size:the max size of the array.
 */
PHeap::PHeap(int size)
{
	maxSize = size;
	initial();
}

void PHeap::initial()
{
	if(maxSize>0){
		allNodes = new PHeapNode * [maxSize];
		for(int i=0; i<maxSize; i++){
			allNodes[i] = 0;
		}
	}
	currentSize = 0;
	min = 0;
}
/*
 *Destructor
 */
PHeap::~PHeap(void)
{
	delete [] allNodes;
}

/*
 *Meld a new paring Heap rooted at nowNode into the current PHeap.
 *After meld, the new min element will be the smaller one of the current min and newNode.
 *PHeapNode * newNode: the root of the new PHeap that need to be melded
 */
void PHeap::meld(PHeapNode * newNode){
	if(min==0){
		min = newNode;
	}
	else{
		PHeapNode * big = (newNode->dist > min->dist) ? newNode : min;
		PHeapNode * small = (newNode->dist <= min->dist) ? newNode : min;


		if(small->child!=0){
			small->child->left = big;		
		}
		big->right = small->child;
		big->left = small;
		small->child = big;
		min = small;
	}
	min->left = 0;
	min->right = 0;
}

/*
 *Insert a new element (node, dist) into the current min Paring Heap.
 *the new min element will be the smaller one of the original min and newNode.
 *int node: the ID of the new node;
 *int dist: the distance from source to node
 *if node is already existed, return -1
 *else, return the current size of PHeap after insert.
 */
int PHeap::insert(int node, int dist)
{
	if(allNodes[node] !=0){
		cout<<"Node "<<node<<" already existed!";
		return -1;
	}
	PHeapNode * newNode = new PHeapNode();
	newNode->child = 0;
	newNode->node = node;
	newNode->dist = dist;
	newNode->left = 0;
	newNode->right = 0;

	//add new node into the top level of the heap
	
	if(currentSize>0)
	{
		meld(newNode);
	}
	else{
		min = newNode;
		//tree_num++;
	}

	allNodes[node] = newNode;
	return ++currentSize;
}

/*
 *Decrease the dist of a certain node, then reconstruct the Pairing Heap
 *int node: the node to decrease value.
 *int newDist: new value of the dist of the node
 */
int PHeap::decreasDist(int node, int newDist){
	PHeapNode * theNode = allNodes[node];
	if(theNode==0){
		cout<<"Node "<<node<<" does not exist!"<<endl;
		return 0;
	}

	theNode->dist = newDist;
	//if theNode is not root,remove it from the children list of its parent and meld 
	if(theNode!=min){
		cut(theNode);
		meld(theNode);			
	}
	return 1;
}

/*
 *Delete current min element from PHeap and then reconstruct the Pairing Heap using 
 *two way merge
 *return
 */
int PHeap::deleteMin()
{
	//cout<<"deleteMin"<<endl;
	int node = min->node;
	PHeapNode * child = min->child;
	delete min;
	min = 0;
	allNodes[node] = 0;
	currentSize--;
	if(child!=0)
	{
		two_wayMerge(child);	
	}
	return node;
}

/*
 *cut a node from its sibling list and meld this node and its children with the original PHeap
 *
 */
void PHeap::cut(PHeapNode * theNode)
{
	if(theNode->left->child==theNode){//theNode is the first child
		theNode->left->child = theNode->right;
		if(theNode->right!=0){
			theNode->right->left = theNode->left;
		}
	}
	else{
		theNode->left->right = theNode->right;
		if(theNode->right!=0){
			theNode->right->left = theNode->left;
		}
	}
	theNode->left = 0;
	theNode->right = 0;
}

/*
 *using two-way merge scheme to merge all the children of the deleted min element
 *PHeapNode * firstChild: the left most child of the original min element
 */
void PHeap::two_wayMerge(PHeapNode * firstChild)
{
	//cout<<"two_wayMerge"<<endl;
	PHeapNode * now = firstChild;
	PHeapNode * right;
	PHeapNode * small;
	PHeapNode * big;

	while(now!=0){	
		right = now->right;
		if(right!=0){
			PHeapNode * next = right->right;
		
			if(now->dist < right->dist){
				small = now;
				big = right;
			}
			else{
				small = right;
				big = now;		
			}

			if(small->child!=0){
				small->child->left = big;		
			}
			big->right = small->child;
			big->left = small;
			small->child = big;
			small->left = 0;
			small->right = 0;

			meld(small);
			now = next;
		}
		else{
			//if there is one last child left
			now->left = 0;
			now->right = 0;
			meld(now);
			now = 0;
		}
	}
}

void PHeap::testPHeap(void)
{

}