固定容量二叉堆

固定容量的二叉堆实现，可用于快速求top k 问题。如要求一个数组中top k的元素，则建立一个容量为k的大根堆，一次遍历数组add进该堆，遍历完毕，堆中的元素即为top k的所有元素。

固定容量大根堆代码

package org.jf.alg;

public class BigHeadFixedBinHeap <T extends Comparable>
{
	private Object array[];
	private int current_size = 0;

	public BigHeadFixedBinHeap(int size)
	{
		array =   new Object[size+1];
	}
	
	/**
	 * 往堆中添加一个元素
	 * 
	 *分两种情况：
	 *1.当前堆未满，直接添加到末尾，回溯保持堆性质
	 *2.当前堆已满，则找出最后一层中最大元素并与当前元素比较，若当前元素小，则替换，否则什么也不做
	 * 
	 * @param data
	 */
	public void add(T data)
	{
		int comp_begin = current_size/2+1;//求最小值的起始位置
		int indx = 1;//记录当前新插入的元素索引
		if(current_size<array.length-1)//堆未满 直接将新元素插入末尾
		{
			array[++current_size]=data;
			indx = current_size;
		}
		else//堆已满 查找最后一层中的最大值
		{
			
			int min_indx = comp_begin;
			T min = (T) array[min_indx];
			int i=comp_begin;
			while(i<array.length)
			{
				if(min.compareTo((T)array[i])>0)
				{
					min_indx = i;
					min = (T) array[min_indx];
				}
				
				i++;
			}
			
			if(min.compareTo(data)<0)
			{
				indx = min_indx;
				array[indx] = data;//当前的最小值被删除了
				
			}
			else
			{
				indx = 1;//不替换
			}
			
		}
		
		//向上检测
		while(indx>1)
		{
			//当前元素与其父节点比较  若小，则交换 indx = indx/2
			//否则 break
			int pdx = indx/2;
			if(((T)array[indx]).compareTo(((T)array[pdx]))>0)
			{
				Object tmp = array[indx];
				array[indx] = array[pdx];
				array[pdx]=tmp;
				indx = pdx;
			}else
			{
				break;
			}
		}
	}
	
	
	/**
	 * 删除堆顶元素
	 * 删除堆顶，用最后一个元素代替堆顶，向下检测保持堆性质
	 * 
	 * @return
	 */
	public T remove()
	{
		T data = null;
		if(current_size==0)
			return null;
		
		
		data = (T) array[1];
		array[1] = array[current_size];
		array[current_size]	= null;
		current_size -- ;

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

		int min_indx =indx;
		Object tmp = null;
		while((min_indx=getMaxIndx(indx))!=indx)
		{
			//indx 与 min_indx元素交换
			tmp = array[indx];
			array[indx]=array[min_indx];
			array[min_indx]=tmp;
			indx = min_indx;
		}
		
		return data;
	}
	
	
	private int getMaxIndx(int indx)
	{
		
		T left = null;
		T right = null;
		if(indx*2>this.current_size)//没有子节点
			return indx;
		if(indx*2==this.current_size)
			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;
	}
	
	public T peek()
	{
		if(this.current_size>0)
		return (T) array[1];
		
		return null;
	}
	

	public int capacity()
	{
		return array.length-1;
	}
	
	 void printArray()
	{
		for(int i=1;i<=this.current_size;i++)
		{
			System.out.print(array[i].toString()+" ");
		}
		System.out.println("\n");
	}
	 
	 public Object [] getAll()
	 {
		 Object[] newArray = new Object[this.current_size];
		 System.arraycopy(array, 1, newArray, 0, current_size);
		 return newArray;
	 }
	
}

固定长度小根堆代码

package org.jf.alg;

/**
 * 定长小根堆
 * 数组存储，数组第一个元素留空
 * 
 * 第k个元素的左儿子为 a[2k],右儿子为a[2k+1]
 * 
 * 第k个元素的父节点为a[k/2]
 * 
 * k从1记起
 * 
 * @author chenjf
 * 
 *
 */
public class LittleHeadFixedBinHeap<T extends Comparable> 
{

	private Object array[];
	private int current_size = 0;

	/**
	 * 
	 * @param size  堆大小
 	 */
	public LittleHeadFixedBinHeap(int size)
	{
		array =   new Object[size+1];

	}
	
	/**
	 * 往堆中添加一个元素
	 * 
	 *分两种情况：
	 *1.当前堆未满，直接添加到末尾，回溯保持堆性质
	 *2.当前堆已满，则找出最后一层中最大元素并与当前元素比较，若当前元素小，则替换，否则什么也不做
	 * 
	 * @param data
	 */
	public void add(T data)
	{
		int comp_begin = current_size/2+1;//求最大值的起始位置
		int indx = 1;//记录当前新插入的元素索引
		if(current_size<array.length-1)//堆未满 直接将新元素插入末尾
		{
			array[++current_size]=data;
			indx = current_size;
		}
		else//堆已满 查找最后一层中的最大值
		{
			
			int max_indx = comp_begin;
			T max = (T) array[max_indx];
			int i=comp_begin;
			while(i<array.length)
			{
				if(max.compareTo((T)array[i])<0)
				{
					max_indx = i;
					max = (T) array[max_indx];
				}
				
				i++;
			}
			
			if(max.compareTo(data)>0)
			{
				indx = max_indx;
				array[indx] = data;//当前的最大值被删除了
				
			}
			else
			{
				indx = 1;//不替换
			}
			
		}
		
		//向上检测
		while(indx>1)
		{
			//当前元素与其父节点比较  若小，则交换 indx = indx/2
			//否则 break
			int pdx = indx/2;
			if(((T)array[indx]).compareTo(((T)array[pdx]))<0)
			{
				Object tmp = array[indx];
				array[indx] = array[pdx];
				array[pdx]=tmp;
				indx = pdx;
			}else
			{
				break;
			}
		}
	}
	
	
	/**
	 * 删除堆顶元素
	 * 删除堆顶，用最后一个元素代替堆顶，向下检测保持堆性质
	 * 
	 * @return
	 */
	public T remove()
	{
		T data = null;
		if(current_size==0)
			return null;
		
		
		data = (T) array[1];
		array[1] = array[current_size];
		array[current_size]	= null;
		current_size -- ;

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

		int min_indx =indx;
		Object tmp = null;
		while((min_indx=getMinIndx(indx))!=indx)
		{
			//indx 与 min_indx元素交换
			tmp = array[indx];
			array[indx]=array[min_indx];
			array[min_indx]=tmp;
			indx = min_indx;
		}
		
		return data;
	}
	
	
	private int getMinIndx(int indx)
	{
		
		T left = null;
		T right = null;
		if(indx*2>this.current_size)//没有子节点
			return indx;
		if(indx*2==this.current_size)
			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;
	}
	
	public T peek()
	{
		if(this.current_size>0)
		return (T) array[1];
		
		return null;
	}
	

	public int capacity()
	{
		return array.length-1;
	}
	
	 void printArray()
	{
		for(int i=1;i<=this.current_size;i++)
		{
			System.out.print(array[i].toString()+" ");
		}
		System.out.println("\n");
	}
	
	 
	 public Object [] getAll()
	 {
		 Object[] newArray = new Object[this.current_size];
		 System.arraycopy(array, 1, newArray, 0, current_size);
		 return newArray;
	 }
}