数据结构与算法---堆的应用场景

前面的文章中介绍了关于数据结构与算法—堆的基本操作，本篇文章中我们再来看看堆的应用场景。

我们知道队列的特性就是先进先出，而优先级队列则是按照某种优先级来的，优先级高的先出，Java中的PriorityQueue就是典型的优先级队列实现，优先级队列通常就是用堆来实现。

找出数组中的最大的前K个数，或者最小的前K个数，我们可以利用大顶堆或者小顶堆来完成。

求数组中最小的K个数

    public int[] smallestK(int[] arr, int k) {
        PriorityQueue queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
        for (int i = 0; i < arr.length; i++) {
            queue.add(arr[i]);
            if (queue.size() > k) {
                queue.poll();
            }
        }

        int[] ans = new int[queue.size()];
        int i = k - 1;
        while (i>=0) {
            ans[i--] = queue.poll();
        }
        return ans;
    }

求中位数就是求一连串数据排序后的中间数，如果数据个数是奇数，那么中位数就是N/2（下标从0开始），如果数据个数是偶数，那么中位数就是(N/2-1+N/2)/2。

用堆实现的方式就是维护两个堆，一个大顶堆和一个小顶堆。如果数据是奇数个，大顶堆就存储N/2+1个数据，小顶堆则存在N/2个数据，如果是偶数，大顶堆和小顶堆就分别存储N/2个数据，最后我们要求，小顶堆中的数据都要大于大顶堆中的数据。

如果新添加的数据小于等于大顶堆的堆顶元素，那么就直接添加到大顶堆，否则就将数据添加到小顶堆，此时可能两个堆的数量不平衡了，如果大顶堆的数据多，那我们就把大顶堆的第一个元素添加到小顶堆，我们小顶堆多，我们就把小顶堆的第一个元素添加到大顶堆，最后我们取中位数时，如果是奇数个，只需要从大顶堆中取出第一个元素即可，如果是偶数个，就分别从大顶堆和小顶堆各取第一个，然后除以2即可。

class MedianFinder {
    PriorityQueue maxQueue = new PriorityQueue<>((o1, o2) -> o2 - o1);
    PriorityQueue minQueue = new PriorityQueue<>();

    public void addNum(int num) {
        if (maxQueue.size() == minQueue.size()) {
            minQueue.add(num);
            maxQueue.add(minQueue.poll());
        } else {
            maxQueue.add(num);
            minQueue.add(maxQueue.poll());
        }
    }

    public double findMedian() {
        if (minQueue.isEmpty()) {
            return maxQueue.peek();
        }
        if (maxQueue.size() == minQueue.size()) {
            return (minQueue.peek() + maxQueue.peek()) / 2.0; 
        } else {
            return maxQueue.peek();
        }
    }
}