fibonacciheap.java

This code implements the shortest path algorithm via the simple scheme and fibonacci heap data struc

public class FibonacciHeap {
	public FibonacciNode root;
	
	public FibonacciHeap(){
		root=null;
	}
	
	public FibonacciHeap(FibonacciNode min){
		root=min;
	}
	
	public boolean isEmpty(){
		//see if the heap is empty
		if(root==null)
			return false;
		else
			return true;
	}
	
	public void Meld(FibonacciHeap f){
		//meld f with the original heap
		FibonacciNode Foriginal;
		FibonacciNode F;
		
		Foriginal=root;
		while(!Foriginal.RightSibling.equals(root))
			Foriginal=Foriginal.RightSibling;
		
		F=f.root;
		while(!F.RightSibling.equals(F))
			F=F.RightSibling;
		
		Foriginal.LeftSibling.RightSibling=F;
		F.LeftSibling.RightSibling=Foriginal;
		FibonacciNode Froot=F.LeftSibling;
		F.LeftSibling=Foriginal.LeftSibling;
		Foriginal.LeftSibling=Froot;
		
		if(f.root.dist<root.dist){
			root=f.root;  
		}
	}
	
	public void Insert(FibonacciNode f){
		//insert f into the orignial heap
		f.LeftSibling=null;
		f.RightSibling=null;
		f.Parent=null;

        //If empty
		if(root==null){
			root=f;
			f.LeftSibling=f;
			f.RightSibling=f;
		}
		else{
			//If there is only one node in the first level
			if(root.RightSibling.equals(root)&& root.LeftSibling.equals(root))
			{
				root.LeftSibling=f;
				root.RightSibling=f;
				f.LeftSibling=root;
				f.RightSibling=root;
			}
			//If there is two or two more node in the first level
			else{
				f.RightSibling=root.RightSibling;
				f.LeftSibling=root;
				root.RightSibling.LeftSibling=f;
				root.RightSibling=f;
			}			
		}
		//If the minroot is less than the node to be inserted, change the minroot pointer
		if(f.dist<root.dist){
			root=f;
		}
	}
	
	private void PairwiseCombine(){
		//pairwise combine two trees with same degree
		if(root==null)
		return;
		if(!root.RightSibling.equals(root)&&!root.LeftSibling.equals(root)){
			int NumOfSibling=0;
			for(FibonacciNode Fnode=root.RightSibling;!Fnode.equals(root);Fnode=Fnode.RightSibling)
				NumOfSibling++;  
			
			FibonacciHeap treetable[]=new FibonacciHeap[1000];
			//initialize the degree table
			FibonacciHeap heap[] = new FibonacciHeap[NumOfSibling+1];;
			boolean combine[]= new boolean[NumOfSibling+1];;
		
			int i=0;
			for(FibonacciNode Fnode=root;i<=NumOfSibling;i++,Fnode=Fnode.RightSibling){
				heap[i]=new FibonacciHeap(Fnode); 
				combine[i]=false;
			}
	
			for(int j=0;j<=NumOfSibling;j++){
				heap[j].root.LeftSibling=heap[j].root;
				heap[j].root.RightSibling=heap[j].root;
				heap[j].root.Parent=null;
			}
			
			for(int j=0;j<=NumOfSibling;j++){
				int degree;
				FibonacciHeap p1;
				FibonacciHeap p2=heap[j];
				degree = heap[j].root.degree;
					
				// combine the heaps until the degree table is null
				while(treetable[degree]!=null)
				{
					p1=treetable[degree];				
					if(p1.root.dist>p2.root.dist){
						int m=0;
						for(int k=0;k<=NumOfSibling;k++){
							if(heap[k].equals(p1)){
								m=k;
							}
						}
						combine[m]=true;
						FibonacciHeap t=p1;
						p1=p2;
						p2=t;
					}
					else{
						int m=0;
						for(int k=0;k<=NumOfSibling;k++){
							if(heap[k].equals(p2)){
								m=k;
							}
						}
						combine[m]=true;
					}
					
					//combine the p1 and p2
					//if p1.min has no children
					if(p1.root.FirstChild!=null)
					{
						//if p1.min has only one first vhild 
						if(p1.root.degree==1){
							p1.root.FirstChild.RightSibling=p2.root;
							p1.root.FirstChild.LeftSibling=p2.root;
							p2.root.RightSibling=p1.root.FirstChild;
							p2.root.LeftSibling=p1.root.FirstChild;
							p2.root.Parent=p1.root;
							p1.root.degree++;
							p2.root.ChildCut=false;

						}
						//if p1.min has two or more than two first children
						else{
							FibonacciNode p=p1.root.FirstChild;
							for(int k=0;k<=p1.root.degree-2&&p.RightSibling!=null;k++){
								p=p.RightSibling;
							}
							p.RightSibling=p2.root;
							p2.root.LeftSibling=p;
							p2.root.RightSibling=p1.root.FirstChild;
							p1.root.FirstChild.LeftSibling=p2.root;
							p1.root.degree++;
							p2.root.ChildCut=false;
							p2.root.Parent=p1.root;
							
						}
					}
					else{
						p1.root.FirstChild=p2.root;
						p2.root.ChildCut=false;
						p2.root.Parent=p1.root;
						p1.root.degree++;
					}
					p2=p1;              
					// make the two heaps become one heap
					treetable[degree]=null; 
					// the orginal degree table set to null
					degree++;  
					// after combinantion, degree increase by 1
				}
				treetable[degree]=p2; 
				// insert the newly combined heap or sole heap in the degree table
			}
			int j;
			for( j=0;j<=NumOfSibling;j++){
				if(combine[j]==false){
					root=heap[j].root; 
					//find the root after pairwise combine
					break;
				}
			}
			for(int k=j+1;k<=NumOfSibling;k++){
				if(combine[k]==false)
					Meld(heap[k]);   
				// link the remaining heaps in the fisrt level
			}
		}
	}
	
	public void RemoveMinroot(){
		//If there is only one node in the first level
		if(root.RightSibling.equals(root)&&root.LeftSibling.equals(root)){
			root=null; // free the root
		}
		
		//If there is two or two nodes in the first level
		else{
			root.LeftSibling.RightSibling=root.RightSibling;
			root.RightSibling.LeftSibling=root.LeftSibling;
			root=root.RightSibling;	
			//If more than one node LeftSibling after deletion
			if(!root.RightSibling.equals(root)&&!root.LeftSibling.equals(root)){
				FibonacciNode Fnode=root,Fnoderoot=root;
				// find the root from the node in the first level
				for(;!Fnode.RightSibling.equals(root);Fnode=Fnode.RightSibling){
					if(Fnode.dist<Fnoderoot.dist){
						Fnoderoot=Fnode;
					}
				}
				root=Fnoderoot;
			}
		}
	}
	
	public FibonacciNode DeleteMin(){
        //If the Heap is Empty
		if(isEmpty()==false)
			return null;
		FibonacciNode Min=root;
        //If root has some FirstChildren
		if(root.FirstChild!=null){		
        //If root has only one FirstChild
			if(root.degree==1){
				FibonacciNode minFirstChild=root.FirstChild;
				RemoveMinroot();
				Insert(minFirstChild);
			}
            //If min has more than one FirstChildren
			else{
				int degree=root.degree-1;
				FibonacciNode minFirstChild=root.FirstChild;
				FibonacciNode FirstChild[]=new FibonacciNode[root.degree];
				// save the root's FirstChildren in a FibonacciNode Array to be inserted later
				for(int i=0;i<=root.degree-1&&minFirstChild!=null;i++,minFirstChild=minFirstChild.RightSibling){
					FirstChild[i]=minFirstChild;
				}
				//after saving the root's FirstChildren, we can delete the root
				RemoveMinroot();
				//insert the remaining FirstChildren into heap in order
				for(int i=0;i<=degree;i++){
					Insert(FirstChild[i]);
				}

			}
		}
		//If the root has no FirstChild
		else{
			RemoveMinroot();
		}
		//combine the remaining heaps pairwise at last
		PairwiseCombine();
		return Min;
	}
	
	private void CutHeap(FibonacciNode x, FibonacciNode P){
		//remove x from first child list of P
		if(P.degree==1){
			P.degree--;
			P.FirstChild=null;
			x.LeftSibling=null;
			x.RightSibling=null;
		}
		else{
			if(P.FirstChild.equals(x)){
				P.degree--;
				P.FirstChild=x.RightSibling;
				x.RightSibling.LeftSibling=x.LeftSibling;
				x.LeftSibling.RightSibling=x.RightSibling;
				x.LeftSibling=null;
				x.RightSibling=null;
			}
			else{
				P.degree--;
				FibonacciNode Fnode=P.FirstChild;
				for(int i=0;i<=P.degree-1&&!Fnode.equals(x);i++,Fnode=Fnode.RightSibling)
					; // find the node x to be cut and cut it
				x.LeftSibling.RightSibling=x.RightSibling;
				x.RightSibling.LeftSibling=x.LeftSibling;
				x.LeftSibling=null;
				x.RightSibling=null;
			}
		}
		//insert x to the first level
		if(root.RightSibling.equals(root)&&root.LeftSibling.equals(root)){
			root.RightSibling=x;
			root.LeftSibling=x;
			x.LeftSibling=root;
			x.RightSibling=root;
		}
		else{
			root.RightSibling.LeftSibling=x;
			x.RightSibling=root.RightSibling;
			root.RightSibling=x;
			x.LeftSibling=root;
		}
		x.Parent=null;
		x.ChildCut=false;  
		// if the node in first level, the attribute ChildCut should be false
	}
	
	private void CascadingCut(FibonacciNode y){
		FibonacciNode Parent=y.Parent;
		if(Parent!=null){
			// if the ChildCut=true, make it false
			if(y.ChildCut==false)
				y.ChildCut=true;  
			else{
				CutHeap(y, Parent);  // cut it from the heap
				CascadingCut(Parent);  // cut it recursively
			}
		}
	}
	
	public void DecreaseKey(FibonacciNode x, int value){
		if(root==null)
			return;
		if(x.LeftSibling!=null&&x.RightSibling!=null){
				x.dist=x.dist-value;
				FibonacciNode y=x.Parent;
				if(y!=null&&x.dist<y.dist){
					CutHeap(x, y); 
					//cut the node from the Parent
					CascadingCut(y); 
					// continue to cut if the Parent's Childcut is ture
				}
			
			if(x.dist<root.dist)
				root=x;
		}
	}

}