使用PriorityQueue来实现最大堆

朴灿烈づ我的快乐病毒、 2021-10-30 04:14 264阅读 0赞

### 题目：最小的k个数 ###

输入n个整数，找出其中最小的k个数。例如输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

主要思路：使用最大堆，保存目前已知的最小的k个数，堆顶是k个数中最大的元素。遍历数组，若堆中元素个数小于k，则直接添加到当前数字到堆中；若当前数字小于堆顶元素（即堆中最大元素），说明堆顶元素不可能是最小的k个数之一，因此用当前数字替换掉堆顶元素，然后保持堆有序（即最大元素在堆顶）；若当前数字大于堆顶元素，说明当前数字不可能是最小的k个数之一，跳过该数字。

> **Java最大堆API**：可使用**优先队列**来实现最大堆。需要设置比较器为**逆序：**
> 
>     Queue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder()); 
> 
> **PriorityQueue：**默认是**最小堆 ，**需要设置过之后，才能成为最大堆。

扩展：使用最大堆（或最小堆）查找最小（或最大）的k个数，比较适合处理海量数据。因为内存的限制，通常不能一次全部载入所有输入数据到内存中。因此，可以每次只读取一部分数据，使用堆来维持目前已知的状态。

关键点：最大堆，最小堆，前k个数

时间复杂度：O(nlog(k))，维持堆有序需要O(log(k))

public class LeastNumbersOfK
    {
        public static void main(String[] args)
        {
            int[] input = {4, 5, 1, 6, 2, 7, 3, 8};
            int k = 4;
            ArrayList<Integer> result = getKthLeastNumbers(input, k);
            System.out.println(result);
        }
    
        private static ArrayList<Integer> getKthLeastNumbers(int[] input, int k)
        {
            if (input == null) return new ArrayList<>();
            int length = input.length;
            if (length == 0 || k <= 0 || k > length) return new ArrayList<>();
            //最大堆
            Queue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
            for (int currentValue : input)
            {
                if (maxHeap.size() < k)
                {
                    maxHeap.add(currentValue);
                } else
                {
                    //当前值比最大堆中的最大值小，则用当前值替换最大值
                    if (currentValue < maxHeap.peek())
                    {
                        maxHeap.poll();  //移除最大值
                        maxHeap.add(currentValue);  //添加当前值
                    }
                }
            }
            return new ArrayList<>(maxHeap);
        }
    }