minheap.java

通过分支限界的方法

class MinHeap {
	/**
	 * AliveNode[] Heap //存放最小堆元素的数组
	 * maxSize //最小堆最多允许元素个数
	 * currentSize //最小堆当前元素个数
	 */
    AliveNode[] Heap;
	int maxSize;
	int currentSize;
	    public MinHeap() {
    	maxSize = 15;
		Heap = new AliveNode[maxSize];
		currentSize = 0;
    }
    
public MinHeap(int n)
{
    	maxSize = 15 < n ? n : 15;
		Heap=new AliveNode[maxSize];
		currentSize=0;
    }
    
public MinHeap(AliveNode[] 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("无左孩子");
    		return 0;
    	}
    	else return 2 * pos + 1;
}

public int rightChild(int pos)
{
    	if(pos >= (currentSize - 1) / 2){
    		System.out.println("无右孩子");
    		return 0;
    	}
    	else return 2 * pos + 2;
}

    public int parent(int pos){
    	if(pos <= 0){
    		System.out.print("无父结点");
		   	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("位置非法");
    	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(AliveNode[] heap,int pos,int j)
{
    	AliveNode temp=heap[pos];
		heap[pos]=heap[j];
	    heap[j]=temp;
}

public void insert(AliveNode 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 AliveNode removeMin()
{
    	if(currentSize<=0)
			System.out.println("堆为空!");
		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;
}
}
}