求最小的k个数问题

查找最小的k个元素
题目：输入n个整数，输出其中最小的k个。
例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。

我的思路：利用二叉堆，构建一个容量为k的定长最小二叉堆，遍历数组，逐个将元素add进堆，完毕返回堆中所有元素即为最小的k个元素

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];

	}
	
	public LittleHeadFixedBinHeap(int size,T []data_array)
	{
		array = new Object[size+1];
		for(int i=0;i<data_array.length;i++)
		{
			this.add(data_array[i]);
		}
	}
	
	/**
	 * 往堆中添加一个元素
	 * 
	 *分两种情况：
	 *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;
	 }
	 
	 
	 public static void main(String args[])
	 {
		 Integer array[] = new Integer[]{3,5,2,6,7,-1,8,0,9,-10};
		 LittleHeadFixedBinHeap heap = new LittleHeadFixedBinHeap(5,array);
		 heap.printArray();
	 }
	  
}

评论

2 楼 cjf068 2012-02-19  

LuckYes 写道

楼主如果用最小堆的话，最好用调整堆的方式来构建堆，这样效率更高以及更容易理解。
public static void Sort(int[] a){
        int temp;
        int n = a.length;
        Display(a);
       
        for(int i = n/2-1;i>=0;i--)                        //从非叶子节点开始
            Adjust(a, i, n);
                                        //初始化堆
        for(int i = n-1;i > 0;i--){
            temp = a[0];                                //交换根节点与最后一个叶子节点，要调整的范围减1
            a[0] = a[i];
            a[i] = temp; 
            Adjust(a, 0, i);                           //不断减小长度、 交换、调整
        }   
        Display(a);
    }
   
    public static void Adjust(int[] a, int i, int n){     //调整函数，参数含义 代表从哪个节点开始跳着，n代表堆的长度范围
        int j = 2*i+1;                                    //从要调整的节点的子节点开始
        int temp = a[i];                                // temp 记录要调整的节点
        while(j<n){                                        //还有叶子节点怎循环
            if(j<n-1 && a[j]<a[j+1])                    //保证不越界，选择两子重的较大者
                j++;
            if(temp >= a[j])                            //根节点较大，停止调整
                break;
            a[(j-1)/2] = a[j];                            //子节点较大，本应该交换，但覆盖即可，temp保存着交换后该节点的信息
            j = j*2+1;                                    //继续检查子节点是否需要交互，如果越界则表明没有子节点
        }
        a[(j-1)/2] = temp;                                //最后停下来的位置上赋上原始节点的值
    }
   

呵呵 谢谢提醒，其实应该用最大堆，每次和堆顶元素比较，发帖之后我想起来了，后来没改

1 楼 LuckYes 2012-02-19  

楼主如果用最小堆的话，最好用调整堆的方式来构建堆，这样效率更高以及更容易理解。
public static void Sort(int[] a){
        int temp;
        int n = a.length;
        Display(a);
       
        for(int i = n/2-1;i>=0;i--)                        //从非叶子节点开始
            Adjust(a, i, n);
                                        //初始化堆
        for(int i = n-1;i > 0;i--){
            temp = a[0];                                //交换根节点与最后一个叶子节点，要调整的范围减1
            a[0] = a[i];
            a[i] = temp; 
            Adjust(a, 0, i);                           //不断减小长度、 交换、调整
        }   
        Display(a);
    }
   
    public static void Adjust(int[] a, int i, int n){     //调整函数，参数含义 代表从哪个节点开始跳着，n代表堆的长度范围
        int j = 2*i+1;                                    //从要调整的节点的子节点开始
        int temp = a[i];                                // temp 记录要调整的节点
        while(j<n){                                        //还有叶子节点怎循环
            if(j<n-1 && a[j]<a[j+1])                    //保证不越界，选择两子重的较大者
                j++;
            if(temp >= a[j])                            //根节点较大，停止调整
                break;
            a[(j-1)/2] = a[j];                            //子节点较大，本应该交换，但覆盖即可，temp保存着交换后该节点的信息
            j = j*2+1;                                    //继续检查子节点是否需要交互，如果越界则表明没有子节点
        }
        a[(j-1)/2] = temp;                                //最后停下来的位置上赋上原始节点的值
    }