求整数数组最大k个数-堆排

有多种方法可以求topK问题：

（1）先全局排序，然后取最大的topK，时间复杂度为O(NlogN) (注：N为数组长度)

（2）部分排序：

     a、冒泡、选择排序 排序过程中依次选出topK个元素,时间复杂度O(kN)
     b、快排partition 划分思想 ，时间复杂度为O(N)

（3）最小堆：时间复杂度为O(Nlogk)

以下使用最小堆解决topK问题。

任务：返回最大的前k个数
输入：array: 包含原始数据的整数数组，k: 要返回的前最大值的个数
输出：array中最大的k个值

步骤：
1、初始化一个大小为k的最小堆 PQ=PriorityQueue(k)
2、for item in array:
    if size(PQ)<k then:
          PQ.add(item）
    else
          if item > 堆顶元素 then:
              删除堆顶元素
              PQ.add(item）
          else:
              舍弃item，什么也不做

3、依次取出堆中的k个元素，即为最大的k个数

java示例代码：

import java.util.PriorityQueue;

public class TopK {
    public static void main(String[] args) {
        // 构造一个大小为k的最小堆
        //（1）当size(堆)<k 时，直接将元素添加进堆中
        //（2）当size(堆)<k 时 如果新加入的元素比堆顶的值更大，则删除堆顶元素，并将元素加入； 如果新加入的元素比堆顶元素还小，则什么也不做。
        int topK = 3;
        int[] arr = new int[] {2, 8, 4, 6, 1, 7, 9, 3, 5, 10};
        //构造一个大小为3的最小堆
        PriorityQueue<Integer> queue = new PriorityQueue<>(topK);
        int count = 0;
        for (int data : arr) {
            if (count < topK) {
                queue.add(data);
            } else {
                int min = queue.peek();
                if (data > min) {
                    queue.poll();
                    queue.add(data);
                }
            }
            count++;
        }
        System.out.println("3th max=>" + queue.poll()); //8
        System.out.println("2th max=>" + queue.poll()); //9
        System.out.println("1th max=>" + queue.poll()); //10
    }
}