minheap.java

《算法设计与分析》王晓东编著

public class MinHeap {
	static Comparable[] heap;
	static int Len;
	
	public MinHeap()
	{
		heap=null;
		Len=0;
	}
	
	public MinHeap(int n)
	{
		heap=new Comparable[n];
		Len=0;
	}
	
	/* 初始化堆结构 */
	public void initialize(Comparable[] comp, int n)
	{
		if (heap==null || heap.length<n) heap=new Comparable[n];
		Len=n;
		for (int i=0;i<n;i++) 
		{
			heap[i]=comp[i];
			int j=i;
			while (j>0 && heap[j].compareTo(heap[j/2])==-1)
			{
				Comparable temp=heap[j];
				heap[j]=heap[j/2];
				heap[j/2]=temp;
				j=j/2;
			}
		}		
	}
	
	/* 输出最小元素，并重建堆 */
	public Comparable removeMin()
	{
		Comparable Min=heap[0];
		
		heap[0]=heap[Len-1];
		Len--;
		
		int j=0;
		while (j<Len)
		{	
			if (j*2<Len && heap[j*2].compareTo(heap[j])==-1
				&& (j*2+1<Len && heap[j*2].compareTo(heap[j*2+1])<=0
					|| j*2+1>=Len))  // 如果heap[j*2]最小
			{
				Comparable temp=heap[j];
				heap[j]=heap[j*2];
				heap[j*2]=temp;
				j=j*2;
			}	
			else
			if (j*2+1<Len && heap[j].compareTo(heap[j*2+1])==1 
				&& heap[j*2].compareTo(heap[j*2+1])>=0) // 如果heap[j*2+1]最小
			{
				Comparable temp=heap[j];
				heap[j]=heap[j*2+1];
				heap[j*2+1]=temp;
				j=j*2+1;
			}
			else break;			
		}
		
		return Min;
	}
	
	/* 插入新元素，重建堆 */
	public void put(Comparable comp)
	{
		Len++;
		if (Len>heap.length)
		{
			Comparable[] newcomp=new Comparable[Len];
			for (int i=0;i<Len-1;i++)
				newcomp[i]=heap[i];
			heap=newcomp;
		}
		
		heap[Len-1]=comp;
		int j=Len-1;
		while (j>0 && heap[j].compareTo(heap[j/2])==-1)
		{
			Comparable temp=heap[j];
			heap[j]=heap[j/2];
			heap[j/2]=temp;
			j=j/2;
		}		
	}
}