minheap.java

分支限界法 单源最短路径问题的 JAVA实现 3个源文件

/**
 * @(#)MinHeap.java
 *
 *
 */


class MinHeap {
	/**
	 *@param HeapNode[] Heap 存放最小堆元素的数组
	 *@param int maxSize 最小堆最多允许元素个数
	 *@param int currentSize 最小堆当前元素个数
	 */
    HeapNode[] Heap;
	int maxSize;
	int currentSize;
	
    public MinHeap() {
    	maxSize = 15;
		Heap = new HeapNode[maxSize];
		currentSize = 0;
    }
    public MinHeap(int n){
    	maxSize = 15 < n ? n : 15;
		Heap=new HeapNode[maxSize];
		currentSize=0;
    }
    public MinHeap(HeapNode[] heap,int n){
    	maxSize = 15 < n ? n : 15;
		Heap=heap;
		currentSize=n;
		buildHeap();
    }
    public int heapSize(){
    	return currentSize;
    }
    public boolean isLeaf(int pos){
    	return (pos >= currentSize / 2)&&(pos < currentSize);
    }
    public int leftChild(int pos){
    	if(pos >= currentSize / 2){
    		System.out.println("the position has no leftchild");
    		return 0;
    	}
    	else return 2 * pos + 1;
    }
    public int rightChild(int pos){
    	if(pos >= (currentSize - 1) / 2){
    		System.out.println("the position has no rightchild");
    		return 0;
    	}
    	else return 2 * pos + 2;
    }
    public int parent(int pos){
    	if(pos <= 0){
    		System.out.print("the position has no parent");
		   	return 0;	
    	}
    	else return (pos -1) / 2;
    }
    public void buildHeap(){
    	for(int i = currentSize / 2;i >= 0;i--)
    		siftdown(i);
    }
    public void siftdown(int pos){
    	if(pos < 0 || pos >= currentSize)
    		System.out.println("illegal heap position");
    	else
    		while(!isLeaf(pos)){
    			int j=leftChild(pos);
		        if((j<(currentSize-1))&&(Heap[j].length>Heap[j+1].length))
				j++;
				if(Heap[pos].length<=Heap[j].length)return;
				swap(Heap,pos,j);
				pos=j;
    		}
    }
    public void swap(HeapNode[] heap,int pos,int j){
    	HeapNode temp=heap[pos];
		heap[pos]=heap[j];
	    heap[j]=temp;
    }
    public void insert(HeapNode val){
    	int curr=currentSize++;
		Heap[curr]=val;
		while((curr!=0)&&(Heap[curr].length <Heap[parent(curr)].length)){
			swap(Heap,curr,parent(curr));
			curr=parent(curr);
		}
    }
    public HeapNode removeMin(){
    	if(currentSize<=0)
			System.out.println("removing from the empty heap!");
		else
			swap(Heap,0,--currentSize);
			if(currentSize!=0)
				siftdown(0);
			return Heap[currentSize];
    }
    public boolean isEmpty(){
    	if(this.currentSize == 0)
    		return true;
    	else return false;
    }
    
    
}