采用PriorityQueue实现大小顶堆 解决topK问题

java.util

类 PriorityQueue

java.lang.Object
——继承者 java.util.AbstractCollection
———– 继承者 java.util.AbstractQueue
—————–继承者 java.util.PriorityQueue

类型参数：
E - collection 中所保存元素的类型。
所有已实现的接口：
Serializable, Iterable, Collection, Queue

public class PriorityQueue<E>
    extends AbstractQueue<E>
    implements Serializable

一个基于优先级堆的*优先级队列。优先级队列的元素按照其自然顺序进行排序，或者根据构造队列时提供的 Comparator 进行排序，具体取决于所使用的构造方法。优先级队列不允许使用 null 元素。依靠自然顺序的优先级队列还不允许插入不可比较的对象（这样做可能导致 ClassCastException）。

此队列的头 是按指定排序方式确定的最小 元素。如果多个元素都是最小值，则头是其中一个元素——选择方法是任意的。队列获取操作 poll、remove、peek 和 element 访问处于队列头的元素。

优先级队列是*的，但是有一个内部容量，控制着用于存储队列元素的数组大小。它通常至少等于队列的大小。随着不断向优先级队列添加元素，其容量会自动增加。无需指定容量增加策略的细节。

此类及其迭代器实现了 Collection 和 Iterator 接口的所有可选 方法。方法 iterator() 中提供的迭代器不 保证以任何特定的顺序遍历优先级队列中的元素。如果需要按顺序遍历，请考虑使用 Arrays.sort(pq.toArray())。

注意，此实现不是同步的。如果多个线程中的任意线程修改了队列，则这些线程不应同时访问 PriorityQueue 实例。相反，请使用线程安全的 PriorityBlockingQueue 类。

实现注意事项：
此实现为排队和出队方法（offer、poll、remove() 和 add）提供 O(log(n)) 时间；
为 remove(Object) 和 contains(Object) 方法提供线性时间；
为获取方法（peek、element 和 size）提供固定时间。

此类是 Java Collections Framework 的成员。

选择最大的K个数

用PriorityQueue默认是自然顺序排序，要选择最大的k个数，构造小顶堆，每次取数组中剩余数与堆顶的元素进行比较，如果新数比堆顶元素大，则删除堆顶元素，并添加这个新数到堆中。

Java中的PriorityQueue来实现堆，用PriorityQueue的实现的代码如下：

public class findTopK {

    //找出前k个最大数，采用小顶堆实现
    public static int[] findKMax(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(k);//队列默认自然顺序排列，小顶堆，不必重写compare

        for (int num : nums) {
            if (pq.size() < k) {
                pq.offer(num);
            } else if (pq.peek() < num) {//如果堆顶元素 < 新数，则删除堆顶，加入新数入堆
                pq.poll();
                pq.offer(num);
            }
        }

        int[] result = new int[k];
        for (int i = 0; i < k&&!pq.isEmpty(); i++) {
            result[i] = pq.poll();
        }
        return result;
    }

 public static void main(String[] args) {
        int[]arr=new int[]{1, 6, 2, 3, 5, 4, 8, 7, 9};
        System.out.println(Arrays.toString(findKMax( arr,5)));
    }
}
/**
输出：[5, 6, 7, 8, 9]
*/

选择最小的K个数

选择最小的k个数可以用冒泡排序，复杂度为O(n*k)，有点高。
要选择最小的K个数使用大顶堆，每次取数组中剩余数与堆顶的元素进行比较，如果新数比堆顶元素小，则删除堆顶元素，并添加这个新数到堆中。

Java中的PriorityQueue来实现堆，用PriorityQueue的实现的代码如下：

public class findTopK {

    ////要找前k个最小数，则构建大顶堆，要重写compare方法
    public static int[] findKMin(int[] nums, int k) {

        PriorityQueue<Integer> pq =
                new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });

        for (int num : nums) {
            if (pq.size() < k) {
                pq.offer(num);
            } else if (pq.peek() > num) {//如果堆顶元素 > 新数，则删除堆顶，加入新数入堆
                pq.poll();
                pq.offer(num);
            }
        }

        int[] result = new int[k];
        for (int i = 0; i < k&&!pq.isEmpty(); i++) {
            result[i] = pq.poll();
        }
        return result;
    }

    public static void main(String[] args) {
        int[]arr=new int[]{1, 6, 2, 3, 5, 4, 8, 7, 9};
        System.out.println(Arrays.toString(findKMin( arr,5)));
    }

}
/**
输出：[5, 4, 3, 2, 1]
*/