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

问题描述：有N(N>>10000)个整数,求出其中的前K个最大的数。（称作Top k或者Top 10）

　　问题分析：由于(1)输入的大量数据；(2)只要前K个，对整个输入数据的保存和排序是相当的不可取的。

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

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

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

 以下为代码实现

/**
 * @author chengtonghua
 * @date 2020-11-17
 */
@SpringBootTest
@RunWith(JUnit4.class)
public class TopKInHeap {
    
    @Test
    public void heap() {
        int[] list = new int[100];
        for(int i=0;i<100;i++){
            list[i]=new Random().nextInt(100);
        }
        Arrays.stream(list).forEach(item ->{
            System.out.println(item);
        });
        solutionByHeap(list,10);
    }

    public List<Integer> solutionByHeap(int[] input, int k) {
        List<Integer> list = new ArrayList<>();
        if (k > input.length || k == 0) {
            return list;
        }
        Queue<Integer> queue = new PriorityQueue<>();
        for (int num : input) {
            if (queue.size() < k) {
                queue.add(num);
            } else if (queue.peek() < num){
                queue.poll();
                queue.add(num);
            }
        }
        while (k-- > 0) {
            list.add(queue.poll());
        }
        System.out.println("--------------------------");
        list.forEach(item ->{
            System.out.println(item);
        });
        return list;
    }
}

PriorityQueue（优先队列参考）https://blog.csdn.net/u010623927/article/details/87179364