Java 详细讲解用堆解决Top-k问题

问题描述

Top-k问题常常需解决业务中的热点，如商品销量排行、热搜关键词、热门文章等。假定要找出一个无序数组中前k大或前k小的元素，解决此问题有多种方法，下面我们主要介绍用堆排序算法解决Top-k问题。

思路及实现

1. 思路

用堆排序算法的思路如下：

1. 建立一个大小为k的堆，如果堆里面元素数量未达到k，那么将当前元素加入堆中即可
2. 如果当前元素大于堆顶元素，那么将堆顶元素替换成当前元素
3. 遍历完整个数组后，堆中的元素就是前k大或前k小的元素

用大根堆求前k大的数，用小根堆求前k小的数。

2. 实现

下面是用Java实现Top-k问题的示例代码：

public class TopK {
    /**
     * 求数组中前k大的数
     *
     * @param nums 数组
     * @param k    k的大小
     * @return 前k大元素的List
     */
    public List<Integer> getTopK(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);

        for (int num : nums) {
            if (minHeap.size() < k) {
                minHeap.offer(num);
            } else if (num > minHeap.peek()) {
                minHeap.poll();
                minHeap.offer(num);
            }
        }

        return new ArrayList<>(minHeap);
    }

    /**
     * 求数组中前k小的数
     *
     * @param nums 数组
     * @param k    k的大小
     * @return 前k小元素的List
     */
    public List<Integer> getLowK(int[] nums, int k) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, Collections.reverseOrder());

        for (int num : nums) {
            if (maxHeap.size() < k) {
                maxHeap.offer(num);
            } else if (num < maxHeap.peek()) {
                maxHeap.poll();
                maxHeap.offer(num);
            }
        }

        return new ArrayList<>(maxHeap);
    }
}

上面代码中，我们用Java内置的优先队列PriorityQueue来实现堆排序，函数offer()用于插入堆中元素，函数poll()用于删除堆顶元素，而peek()则用于查看堆顶元素而不删除它。

接下来我们用一个数组和getTopK()函数来演示求前k大的数：

public static void main(String[] args) {
    int[] nums = {1, 3, 2, 5, 4, 8, 6, 0};
    int k = 4;

    TopK topK = new TopK();
    List<Integer> topKList = topK.getTopK(nums, k);

    System.out.println("前" + k + "大的的数为：" + topKList.toString());
}

控制台输出结果为：前4大的的数为：[3, 4, 5, 6]，即数组中前4大的数是3, 4, 5, 6。

接着，我们来演示用getLowK()函数来求前k小的数：

public static void main(String[] args) {
    int[] nums = {1, 3, 2, 5, 4, 8, 6, 0};
    int k = 4;

    TopK topK = new TopK();
    List<Integer> lowKList = topK.getLowK(nums, k);

    System.out.println("前" + k + "小的的数为：" + lowKList.toString());
}

控制台输出结果为：前4小的的数为：[1, 0, 2, 3]，即数组中前4小的数是1, 0, 2, 3。

以上示例代码和输出结果，均说明用堆排序算法可以很方便地解决Top-k问题。

小结

用堆排序算法解决Top-k问题，是一种时间复杂度为O(nlogk)的高效算法，它也是解决业务中Top-k问题的常用方法之一。

我们注意到PriorityQueue由于使用了大常数，堆排序的复杂度与快速排序相近：O(n * logn)，但优于冒泡排序的O(n^2)。