使用PriorityQueue创建大小堆，解决TOPK问题

集合框架中的PriorityQueue底层使用堆结构因此其内部的元素必须要能够比大小PriorityQueue采用了 Comparble和Comparator两种方式。1. Comparble是默认的内部比较方式如果用户插入自定义类型对象时该类对象必须要实现Comparble接 口并覆写compareTo方法2. 用户也可以选择使用比较器对象如果用户插入自定义类型对象时必须要提供一个比较器类让该类实现 Comparator接口并覆写compare方法。创建大小堆先实现比较器//小根堆 class LessComp implements ComparatorInteger { Override public int compare(Integer o1, Integer o2) { return o1 - o2; } } //大根堆 class GreaterComp implements ComparatorInteger { Override public int compare(Integer o1, Integer o2) { return o2 - o1; } }例如找到最大的k个数public int[] maxKey(int[] array, int k) { if(k 0){ return null; } LessComp gc new LessComp(); PriorityQueueInteger pq new PriorityQueue(gc); for(int i 0; i k; i){ pq.offer(array[i]); } for(int i k; i array.length; i){ int top pq.peek(); if(top array[i]){ pq.poll(); pq.offer(array[i]); } } int[] result new int[k]; for(int i 0; i k; i){ result[i] pq.poll(); } return result; }要维护一个长度为k的小根堆堆顶是堆里最小的数然后开始比较将大于堆顶的数入队内部会进行向上调整依次将剩下的数据处理。本例是找最大的k个数要维护一个小根堆反之找最小的k个数就维护一个大根堆。但要注意入堆的条件。当维护小根堆的时候只有当新数据比堆顶大时才入堆。最大的前k个数当维护大根堆的时候只有当新数据比堆顶小时才入堆。最小的前k个数