大根堆

大根堆，可用于优先级队列

package org.jf.alg;

/**
 * 大根堆
 * 
 * @author junfeng.chen
 *
 * @param <T>
 */
public class BigHeadBinaryHeap <T extends Comparable>
{
	private int step = 64;
	private Object [] array;
    private int last_indx = 0;
	public BigHeadBinaryHeap(int initial_size,int step)
	{
		if(step>0)
		this.step = step;
		array = new Object[initial_size+1];
	}
	
	
	public BigHeadBinaryHeap()
	{
		array = new Object[33];
	}
	
	
	public void push(T data)
	{
		if(this.last_indx==array.length-1)
		{
			Object newarray []= new Object[array.length+this.step]; 
			System.arraycopy(array, 1, newarray, 1, array.length-1);
			array = newarray;
		}
		array[last_indx+1] = data;
		last_indx ++;
		
		int indx = last_indx;
		while(indx>1)//向上检查 保证满足堆性质
		{
			int pdx = indx/2;//父亲 index
			if(((T)array[indx]).compareTo(((T)array[pdx]))>0)
			{
				Object tmp = array[indx];
				array[indx] = array[pdx];
				array[pdx]=tmp;
				indx = pdx;
			}else
			{
				break;
			}
		}
		
	}
	
	public T pop()
	{
		T data = null;
		if(last_indx==0)
			return null;
		
		
		data = (T) array[1];
		array[1] = array[last_indx];
		array[last_indx]	= null;
		last_indx -- ;

		//根节点与左右子节点中最小元素交换
		
		int indx = 1;

		int max_indx =indx;
		Object tmp = null;
		while((max_indx=getMaxIndx(indx))!=indx)
		{
			//indx 与 min_indx元素交换
			tmp = array[indx];
			array[indx]=array[max_indx];
			array[max_indx]=tmp;
			indx = max_indx;
		}
		
		return data;
	
	}
	
	private int getMaxIndx(int indx)
	{
		
		T left = null;
		T right = null;
		if(indx*2>this.last_indx)//没有子节点
			return indx;
		if(indx*2==this.last_indx)
			left = (T)array[indx*2];
		else
		{
			left = (T)array[indx*2];
			right =(T)array[indx*2+1];
		}
		
		
		if(right==null)
		{
		
			if(left.compareTo((T)array[indx])>0)
				indx =  indx*2;
		}else
		{
			
			if(left.compareTo((T)array[indx])>0)
			{
				indx = indx*2;
				if(right.compareTo((T)array[indx])>0)
					indx = indx+1;
			}
			else if(right.compareTo((T)array[indx])>0)
			{
				indx = indx*2+1;
			}
			
			
		}
		
		return indx;
	}
	 void printArray()
		{
			for(int i=1;i<=this.last_indx;i++)
			{
				System.out.print(array[i].toString()+" ");
			}
			System.out.println("\n");
		}
	 
	public T peek()
	{
		if(this.last_indx>0)
		return (T) array[1];
		return null;
	}
	
	public boolean isEmpty()
	{
		return last_indx==0;
	}
	
	public int size()
	{
		return last_indx;
	}
	
	public Object[] getAll()
	{
		Object newArray[] = new Object[this.last_indx];
		System.arraycopy(array, 1, newArray, 0, last_indx);
		return newArray;
	}
}