topK

• 1、找出最小的k个数
  输入n个数，找出其中最小的k个数

1. 使用快速排序中的partition函数，时间复杂度为o（n）,需调整数组位置
   每进行一轮排序看返回的结点是否为第k个数，若为，则k左边都比k小，k右边都比k大，这时返回前k个数就好了

void getLeaseNumbers(int []input,int n,int k){
  int[] output=new int[k];
  if(input==null||k>n||n<=0||k<=0)return ;
  int start=0;
  int end=n-1; 
  int index =Partition(input,n,start,end);
  while(index!=k-1){
    if(index>k-1){
      end=index-1;
      index = Partition(input,n,start,end);
    }else{
      start=index+1;
      index = Partition(input,n,start,end);  
    }
  }
  for(int i=0;i<k;i++){
    output[i]=input[i];
  }
}

2)若初始数组不能允许排序，则可使用一个大根堆进行实现。时间复杂度为o(nlogk)，适合海量数据
首先构建一个容量为k的堆，然后从n个数据中继续读取数据，大根堆中的堆顶为最大值，将该值和从n中取出的值相比较，若堆顶元素更大，则将其删除，插入从n中取出的数据，然后再调整堆。
3）使用PriorityQueue模拟大根堆
http://blog.csdn.net/jiutianhe/article/details/41441881

 public class FixSizedPriorityQueue <E extends Comparable<E>>{
    private PriorityQueue<E> queue;
    private int maxSize;// 堆的最大容量
    public FixSizedPriorityQueue(int maxSize) {
        if(maxSize <=0){
            throw new IllegalArgumentException();
        }
        this.maxSize = maxSize;
        this.queue =new PriorityQueue<E>(maxSize,new Comparator<E>() {
            // 生成最大堆使用o2-o1,生成最小堆使用o1-o2, 并修改 e.compareTo(peek) 比较规则
            public int compare(E o1, E o2) {                
                return(o2.compareTo(o1));
            }
        });
    }
    public void add(E e){
        if(queue.size() < maxSize) {// 未达到最大容量，直接添加
            queue.add(e);
        }else{// 队列已满
            E peek = queue.peek();
            if(e.compareTo(peek) <0) {// 将新元素与当前堆顶元素比较，保留较小的元素
                queue.poll();
                queue.add(e);
            }
        }
    }