每日写题分享–优先队列

还记得Java优先队列吗，进来复习复习..

Java中优先队列默认是小根堆，堆顶元素即队列最小值。

在很多应用中，我们通常需要按照优先级情况对待处理对象进行处理，比如首先处理优先级最高的对象，然后处理次 高的对象。最简单的一个例子就是，在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话。 在这种情况下，我们的数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这 种数据结构就是优先级队列(Priority Queue)。

来实战：

题目描述：

代码实现：

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {  
        int[] res = new int[k];  //结果集   
        if (k == 0) return res;
        PriorityQueue<Integer> pq = new PriorityQueue<>(k,new Comparator<Integer>(){
            public int compare(Integer o1,Integer o2) {
                return o2 - o1;
            }    //Java默认小根堆，更改排序方法为小根堆
        });
        for (int i = 0;i < arr.length;i++) {
            if (i < k) {
                pq.add(arr[i]);    //先将前k个元素入队
            } else {
                if (arr[i] < pq.peek()) {
                    pq.poll();
                    pq.add(arr[i]);    //比堆顶元素大的元素存放进来
                }
            }           
        }       
        for (int i = 0;i < k;i++) {   
            res[i] = pq.poll();
        } 
        return res;
    }
}

 使用优先队列还有一个还出就是随时可以添加新元素，而不需要重新排序，只要将新元素与堆顶元素做一次比较即可。

比如这题：

数据流中的中位数

 这题是要求实现随时添加元素之后求出中位数，同样可以采用优先队列解决。将一组数据分为两段，比中位数小的为前半段，升序排序，即大根堆，堆顶元素就是中位数；比中位数大的为后半段，建立小根堆，堆顶元素就是最小的，也是中位数或者中位数右边元素。所以这里要判断数组长度是奇数还是偶数。长度是偶数则添加元素时添加到前半段，这样前半段的最大值（堆顶元素）就是中位数，长度为奇数时，根据前面操作，前半段的数组长度比后半段大1，添加元素添加到后半段，中位数是两个堆顶元素和的二分之一。当然，添加元素时不能直接添加，因为要保证数组整体有序，所以要先到另一个堆里过滤一遍，挑出最大或者最小的元素添加。

代码实现如下：

class MedianFinder {
    PriorityQueue<Integer> max,min;
    /** initialize your data structure here. */
    public MedianFinder() {
        max = new PriorityQueue<>((o1,o2) -> (o2 - o1));//大根堆，保存较小的一半
        min = new PriorityQueue<>();//小根堆，保存加大的一半
    }
    
    public void addNum(int num) {
        if (max.size() == min.size()) {    //偶数，添加元素到前半段
            min.offer(num);                //先拿到后半段过滤，找到最小值再将最小值添加到前半段，保证整体有序
            max.offer(min.poll());
        } else {                            //奇数，添加元素到后半段
            max.offer(num);                //拿到前半段过滤，找到最大值添加到后半段，保证整体有序
            min.offer(max.poll());
        }
    }
    
    public double findMedian() {
        return max.size() > min.size() ? max.peek() : (max.peek() + min.peek()) / 2.0;
    }
}