欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

10.巩固学习PriorityQueue类------海量数据处理的 Top K算法(问题) 小顶堆实现

程序员文章站 2022-03-15 21:57:24
...

海量数据处理的 Top K算法(问题) 小顶堆实现

问题描述:有N(N>>10000)个整数,求出其中的前K个最大的数。(称作Top k)   
问题分析:由于(1)输入的大量数据;(2)只要前K个。那么对整个输入数据的保存和排序是非常耗时耗内存且没必要的。

可以利用数据结构的最小堆来处理该问题。

最小堆如图所示,对于每个非叶子节点的数值,一定不大于孩子节点的数值。这样可用含有K个节点的最小堆来保存K个目前的最大值(当然根节点是其中的最小数值)。

每次有数据输入的时候可以先与根节点比较。若不大于根节点,则舍弃;否则用新数值替换根节点数值。并进行最小堆的调整。

Java实现如下:

int[] topK(int nums[],int k){
    PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>();
    for (int v:nums) {
        if (priorityQueue.size() < k)
            priorityQueue.add(v);
        else if (priorityQueue.peek() < v) {
            priorityQueue.poll();
            priorityQueue.add(v);
        }
    }
    int[] result = new int[k];
    for (int i = k - 1; i >= 0; i --)
        result[i] = priorityQueue.poll();
    return result;
}