Top K 最大值(最小值)问题

Top K问题指的是从大量数据中获取前K个最大值或者最小值。 我们可以用miniHeap解决TopK最大值问题,或者MaxHeap解决TopK最小值问题, 时间复杂度O(nlogK)。

最小堆解决TopK最大值的解决方法就是:先去源数据中的K个元素放到一个长度为K的数组中去,再把数组转换成最小堆。再依次取源数据中的K个之后的数据和堆的根节点(数组的第一个元素)比较,根据最小堆的性质,根节点一定是堆中最小的元素,如果小于它,则直接pass,大于的话,就替换掉跟元素,并对根元素进行Heapify,直到源数据遍历结束。堆中元素就是TopK的最大元素。

Java 中实现Priority Queue.

 maxPQ = new PriorityQueue<Integer>();
 miniPQ = new PriorityQueue<Integer>(new Comparator<Integer>(){
        public int compare(Integer i1, Integer i2) {
            return i2 - i1;
        }
 });

Reference:
http://blog.csdn.net/xiao__gui/article/details/8687982
http://baozitraining.org/blog/mitbbs-google-k-largest-elements/

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s