优先队列

「堆」是实现「优先队列」的一个高效的数据结构。首先，我们来认识「优先队列」。

优先队列

• 优先队列（Priority Queue）是一种数据结构；

• 堆（Heap）是具体的实现。

  队列与优先队列

• 队列：我们知道「队列」是一种先进先出（FIFO）的数据结构，出队顺序谁先来谁先出去，有点先到先得的意思，日常生活中，随处可见的排队现象，抽象出来，就是「队列」这种数据结构。

• 优先队列：同时，在我们的生活中，有些情况下，并不是按照谁先来，谁先处理的原则来处理事情，例如，我们自己的时间管理，我们会先处理最重要或者是最紧急的事情。又或者是我们非常看不惯的一种现象是，有些服务会针对 VIP 用户优先处理。「优先队列」的思想就类似与我们处理这一类问题的思路，我们按照问题或者任务的重要程度（有的时候称之为优先级），处理觉得更重要，优先级更高的事情，而不是来一个问题就马上处理解决这个问题。 | 普通队列 | 优先队列 | | :—- | :—- | | 先进先出，后进后出。入队的时间顺序决定了出队的顺序。 | 出队顺序与入队顺序无关，只与队列中元素的优先级有关，优先级最高的元素最先出队。 |

• 以下「优先队列」的两个重要操作：1、入队；2、出队。优先队列的一个重要特点是：出队的时候总是取出当前队列里优先级最高的那个元素；

• 那么，什么是「堆」呢？「堆」是「优先队列」的一种实现，除了「堆」以外，我们还可以使用「普通的数组」和「顺序排放的数组」来实现「优先队列」；
• 「优先队列」是更抽象的数据结构；
• 这里我们所说的「堆」，通常是指「二叉堆」。

  三种数据结构对于实现优先队列的时间复杂度的比较

  | 使用什么数据结构来实现优先队列 | 入队操作 | 出队操作 | | —- | —- | —- | | 普通数组 | O(1) | O(n) | | 顺序数组 | O(n) | O(1) | | 堆（就是优先队列） | O(log n) | O(log n) |

其中，log n表示以 2 为底的 n 的对数。于是，我们伟大的计算机科学家平衡了入队和出队这两个操作的时间复杂度，这种数据结构就是堆。
综上所述，堆是一种实现优先队列的高效的数据结构。

堆的基本实现：二叉堆

通过上一小节的介绍，我们可以看到堆的入队和出队的时间复杂度都是O(log n)，因此我们可以猜测它的形状看起来像是一棵树一样。形如下面形状的一个结构就是「最大堆」。
下面演示了几种不是「堆有序」的情况：

「最大堆」的性质

• 首先，「最大堆」是一棵「完全二叉树」；

完全二叉树：从形状上看，除了最后一层之外，其它层结点的数量达到最大值，并且最后一层的结点全部集中在左侧。

「完全二叉树」的特点是：可以使用一个数组保存「完全二叉树」，而不必引入离散的树形结构。这样既可以利用数组元素可以快速访问的特点，又让结点和结点之间形成了「父」与「子」的结构关系。

• 其次，任意一个结点，如果有孩子结点的话，孩子结点的值一定不会大于父亲结点的值。

如果一个数组中的元素，有如上特点，我们称之为堆有序。
堆有序不是我们通常理解意义上的「升序」或者「降序」。如果把数组排成「完全二叉树」的样子，且满足第 2 条，这个数组就是「堆有序」。这里要注意的是，通常我们数组的 0 号下标不使用，从 1 号下标开始使用。
这只是一种习惯，因为这么做父子结点的下标关系更「好看」一些，仅此而已。到从 0 号下标开始使用的堆也是可以的。

下面下标从 1 号开始，自上到下、自左到右标记，即显示成结点的旁边黑色的数字。我们不难发现这些数字的排列形成的规律。
正是因为「堆」是一棵「完全二叉树」，有如下的规律，我们才可以很方便地索引数组中的位置，这就是我们为什么使用数组而不是使用树来实现堆。

上面这张图用数组表示出来，就是一个最大堆。它在我们的程序中是这样表示的：

是不是很酷，在这里我们使用数组来表示了一个树结构，借助了完全二叉树的性质，这一点刚刚接触的时候可能会比较陌生，在以后，接触线段树的时候，我们还会体会这种处理问题的方法。

• 规律 1：一个结点的左结点（如果有的话）的下标是这个结点的编号的 2 倍；

• 规律 2：一个结点的右结点（如果有的话）的下标是这个结点的编号的 2 倍 + 1。

• 从子结点下标找到父结点下标：，注意这里不能整除的时候需要向下取整；

• 从父节点下标找到两个子结点下标：、。

这个两条性质不用记，我们只要拿一张纸，画一个像上面一样图，就非常清楚了。到这里为止，我们可以先写出「最大堆」的主要内容。

// 我们这个版本的实现中，0 号下标是不存数据的，这一点一定要注意
public class MaxHeap {
    private int[] data;
    // 当前堆中存储的元素的个数
    private int count;
    // 堆中能够存储的元素的最大数量（为简化问题，不考虑动态扩展）
    private int capacity;
    // 初始化最大堆
    public MaxHeap(int capacity) {
        // 初始化底层数组元素（ 0 号下标位置不存数据，这是为了使得通过父结点获得左右孩子有更好的表达式）
        data = new int[capacity + 1];
        count = 0;
    }
    // 返回堆中的元素个数
    public int size() {
        return count;
    }
    // 返回一个布尔值，返回堆中是否为空
    public boolean isEmpty() {
        return count == 0;
    }
}

「最大堆」的各种操作

下面我们介绍如何保持「最大堆」数组的堆有序的性质。
最大堆的第 1 个重要操作：向一个「最大堆」中添加元素

• 向「最大堆」中添加一个元素，对应优先队列中「入队」这个操作；
• 同时还要保持「最大堆」的性质，即根元素是「最大堆」中最大的元素；
• 并且除了根结点以外任意一个结点不大于它的父亲结点；
• 这个操作叫做 siftUp 。

为此，向「最大堆」中的添加元素的时候，首先添加在数组的末尾，然后进行调整，使得调整后的数组仍然满足最大堆的性质（这样的操作移动的次数最少）。

具体步骤如下：

• 新加的元素放在数组的末尾；
• 新加入的元素调整元素的位置：只与父结点比较（不必与兄弟孩子比较），如果比父结点大，就交换位置，否则，可以停止了，这个元素就放在当前位置。

问题：为什么我们要在数组的末尾添加一个元素呢？可不可以在开头、中间？

• 这是因为既然我们使用数组来实现堆，对数组添加一个元素来说，实现复杂度最低的操作就是在数组的末尾添加元素；
• 如若不然，要让数组中一部分的元素逐个后移，因此在数组的末尾加入元素是最自然的想法；
• 但是在数组的末尾添加了一个元素，此时的数组就不满足堆的定义（性质）。我们需要进行一系列的操作，去维护堆的定义（性质）。

如何维护堆的定义和性质？

• 通过 siftUp 操作把新添加的元素放置到合适的位置；
• 在数组的最后位置添加一个元素，新加入的元素只和父结点比较大小（无需和它的兄弟结点比较）；
• 只要比父结点大（严格大于），就往上走，否则停止；
• 这个新添加的元素就放置在合适的位置，同时也调整了部分元素的位置；
• 循环这样做，这样的过程叫做 siftUp，siftUp 也叫 swim，是「上浮」的意思。

最大堆的第 2 个重要操作：向从一个最大堆中取出元素

• 根据堆有序的性质，根结点是堆（数组）中最大的元素，即数组里下标为 1 的元素；
• 从最大堆中取出一个元素，即是取出根结点元素，同时还要保持最大堆的性质；
• 根结点取出以后，1 号下标位置为空，于是我们将当前数组的最后一个元素放到 1 号下标的位置。这样做是因为交换和移动的次数最少，这种想法也应该是十分自然的，并且保持了完全二叉树的性质；
• 但是此时数组并不满足最大堆的性质，我们就要进行 siftDown 的操作使这个数组保持最大堆的性质。

siftDown 的具体操作步骤：

• 从 1 号下标开始，如果存在右孩子，就把右孩子和左孩子比较，比出较大的那个，再和自己比较，如果比自己大，就交换位置，这样的过程直到「不小于两个孩子结点中的最大者」。

  LeetCode

  347. 前 K 个高频元素

  给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

思路：

• 要得到出现次数前k高的元素，首先得知道各个元素分别出现了多少次。可以使用 Map numToCount以元素为键，以该元素出现的次数为值，遍历一次原数组即可得到。
• 接下来就是排序，遇到前k高这样的描述，自然想到不必将他们完全排序，可以使用优先队列。要留下最高的k个元素，那么就使用最小优先队列。当队列中元素超过k时就弹出最小的元素，这样当所有元素都入队一次后（这个过程中还有出队），就得到了出现次数最多的元素。
• 但是这样有一个问题：我们在统计出现次数的时候，散列表的键是元素，值是出现次数。我们排序的是次数，但是最终答案不是出现次数，而是元素。所以我们还得将次数映射回元素。会有多个元素出现次数相同，所以用Map来构建映射时不可以的。
• 构建映射，只要键值对放在一起就行，所以想到内置的Pair，将元素与出现次数一起封装到这个类中，以元素为键，以该元素出现的次数为值，然后放入最小优先队列中。最后取出优先队列中剩余的k个元素，取出Pair中的键。
• 在构建最小优先队列时，我们需要传入自定义的Comparator实例来让优先队列按照Pair中的值进行排序。自定义Comparator需要实现实现compare方法。
• 注意优先队列中依次取出的元素是升序排列的，但答案需要降序排列，就将每次取出的元素放在List的第一个元素的位置即可。

• 出现次数的统计是O(n)O(n)的，使用优先队列的操作中，每个元素都入队了，近似认为队列元素一直为k，那么时间复杂度是O(nlog(k))O(nlog(k))的，最后将队列中k个元素放入List中，所需的操作为O(klog(k))O(klog(k))，总体来看时间复杂度为O(nlog(k))O(nlog(k))。

  class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> numToCount = new HashMap<>();
        for(int i : nums) {
            numToCount.put(i, numToCount.getOrDefault(i, 0) + 1);
        }
        PriorityQueue<Pair<Integer, Integer>> minPQ = new PriorityQueue<>(new Order());
        for(int key : numToCount.keySet()){
            minPQ.add(new Pair<>(key, numToCount.get(key)));
            if(minPQ.size() > k) {
                minPQ.remove();
            }
        }
        int[] res = new int[k];
        int ind = k-1;
        while(!minPQ.isEmpty()) {
            res[ind--] = minPQ.remove().getKey();
        }
        return res;
    }
    private class Order implements Comparator<Pair<Integer, Integer>> {
        public int compare(Pair<Integer, Integer> v, Pair<Integer, Integer> w){
            return v.getValue() - w.getValue();
        }
    }
  }

  703. 数据流中的第K大元素

  设计一个找到数据流中第K大元素的类（class）。注意是排序后的第K大元素，不是第K个不同的元素。
  你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器，它包含数据流中的初始元素。每次调用 KthLargest.add，返回当前数据流中第K大的元素。

思路：
维护一个最小堆，最小的值在最上面。堆的大小为 k，这样堆中存放前 k 个最大的元素，堆顶为第 k 大元素。

class KthLargest {
    private PriorityQueue<Integer> minPQ;
    private int size;
    public KthLargest(int k, int[] nums) {
        size = k;
        minPQ = new PriorityQueue<>(k);
        for (int n : nums) {
            add(n);
        }
    }
    public int add(int val) {
        if (minPQ.size() < size) {
            minPQ.add(val);
        } else if (val > minPQ.peek()) {
            minPQ.poll();
            minPQ.add(val);
        }
        return minPQ.peek();
    }
}
/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.add(val);
 */

692. 前K个高频单词

给一非空的单词列表，返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。

思路：
利用最小优先队列，来获取前 k 个高频单词。相同频率的单词要按字母顺序排列，因此comparator中的条件为m2.getKey().compareTo(m1.getKey());，最后的结果按从高到低排列，因此每次添加时添加到开头。

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> strToCount = new HashMap<>();
        for(String s : words) {
            strToCount.put(s, strToCount.getOrDefault(s, 0) + 1);
        }
        PriorityQueue<Pair<String, Integer>> minQue = new PriorityQueue<>(comparator);
        for (String key : strToCount.keySet()) {
            minQue.add(new Pair<>(key, strToCount.get(key)));
            if(minQue.size() > k) {
                minQue.remove();
            }
        }
        List<String> res = new ArrayList<>();
        while(!minQue.isEmpty()) {
            res.add(0, minQue.remove().getKey());
        }
        return res;
    }
    public static Comparator<Pair<String, Integer>> comparator = new Comparator<Pair<String, Integer>>(){
        @Override
        public int compare(Pair<String, Integer> m1, Pair<String, Integer> m2) {
            if (m1.getValue()== m2.getValue()) {
                return m2.getKey().compareTo(m1.getKey());
            } else {
                return m1.getValue() - m2.getValue();
            }
        }
    };
}

练习：

239. 滑动窗口最大值

剑指 Offer

剑指 Offer 40. 最小的k个数

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

思路1：
大根堆(前 K 小) / 小根堆（前 K 大)
保持堆的大小为K，然后遍历数组中的数字，遍历的时候做如下判断：
1. 若目前堆的大小小于K，将当前数字放入堆中。
2. 否则判断当前数字与大根堆堆顶元素的大小关系，如果当前数字比大根堆堆顶还大，这个数就直接跳过；反之如果当前数字比大根堆堆顶小，先poll掉堆顶，再将该数字放入堆中。

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        // 默认是小根堆，实现大根堆需要重写一下比较器。
        Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> v2 - v1);
        for (int num: arr) {
            if (pq.size() < k) {
                pq.offer(num);
            } else if (num < pq.peek()) {
                pq.poll();
                pq.offer(num);
            }
        }

        // 返回堆中的元素
        int[] res = new int[pq.size()];
        int idx = 0;
        for(int num: pq) {
            res[idx++] = num;
        }
        return res;
    }
}

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(arr == null || arr.length == 0 || k == 0) return new int[0];
        int[] result = new int[k];
        int i = 0;
        while(i < k){
            result[i] = arr[i];
            i++;
        }
        buildHeap(result);
        while(i < arr.length){
            if(arr[i] < result[0]){
                result[0] = arr[i];
                adjust(result, 0);
            }
            i++;
        }
        return result;
    }
    public void buildHeap(int[] arr){
        for(int i = arr.length / 2 - 1; i >= 0; i--){
            adjust(arr, i);
        }
    }
    public void adjust(int[] arr, int i){
        int maxIndex = i;
        int len = arr.length;
        if(2*i+1 < len && arr[2*i+1] > arr[maxIndex]) maxIndex = 2*i+1;
        if(2*i+2 < len && arr[2*i+2] > arr[maxIndex]) maxIndex = 2*i+2;
        if(maxIndex != i){
            swap(arr, maxIndex, i);
            adjust(arr, maxIndex);
        }
    }
    public void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

思路2：
快速排序。

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        // 最后一个参数表示我们要找的是下标为k-1的数
        return quickSearch(arr, 0, arr.length - 1, k - 1);
    }

    private int[] quickSearch(int[] nums, int lo, int hi, int k) {
        // 每快排切分1次，找到排序后下标为j的元素，如果j恰好等于k就返回j以及j左边所有的数；
        int j = partition(nums, lo, hi);
        if (j == k) {
            return Arrays.copyOf(nums, j + 1);
        }
        // 否则根据下标j与k的大小关系来决定继续切分左段还是右段。
        return j > k? quickSearch(nums, lo, j - 1, k): quickSearch(nums, j + 1, hi, k);
    }

    // 快排切分，返回下标j，使得比nums[j]小的数都在j的左边，比nums[j]大的数都在j的右边。
    private int partition(int[] nums, int lo, int hi) {
        int v = nums[lo];
        int i = lo, j = hi + 1;
        while (true) {
            while (++i <= hi && nums[i] < v);
            while (--j >= lo && nums[j] > v);
            if (i >= j) {
                break;
            }
            int t = nums[j];
            nums[j] = nums[i];
            nums[i] = t;
        }
        nums[lo] = nums[j];
        nums[j] = v;
        return j;
    }
}

剑指 Offer 41. 数据流中的中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：

• void addNum(int num) - 从数据流中添加一个整数到数据结构中。
• double findMedian() - 返回目前所有元素的中位数。

思路：
维护一个最大堆和最小堆。
当之前的数据流数量为偶数时，比较最大堆的堆顶元素和 num，如果堆顶元素更大，则将 num 插入最大堆，然后弹出最大堆堆顶元素，并将堆顶元素插入最小堆中。如果堆顶元素更小，则直接插入最小堆中。完成插入后最大堆和最小堆共有奇数个数据。因此在返回中位数时，如果数据流数量为奇数，则说明最小堆元素数量大于最大堆，直接返回最小堆堆顶元素。
执行用时：94 ms, 在所有 Java 提交中击败了23.03%的用户
内存消耗：50.7 MB, 在所有 Java 提交中击败了100.00%的用户

class MedianFinder {
    private PriorityQueue<Integer> maxHeap;
    private PriorityQueue<Integer> minHeap;

    public static Comparator<Integer> comparator = new Comparator<Integer>(){
        @Override
        public int compare(Integer n1, Integer n2) {
            return n2 - n1;
        }
    };

    /** initialize your data structure here. */
    public MedianFinder() {
        minHeap = new PriorityQueue<>();
        maxHeap = new PriorityQueue<>(comparator);
    }

    public void addNum(int num) {
        if ((minHeap.size() + maxHeap.size()) % 2 == 0 ) {
            if (!maxHeap.isEmpty() && maxHeap.peek() > num) {
                maxHeap.offer(num);
                num = maxHeap.poll();
            }
            minHeap.offer(num);
        } else {
            if (!minHeap.isEmpty() && minHeap.peek() < num) {
                minHeap.offer(num);
                num = minHeap.poll();
            }
            maxHeap.offer(num);
        }
    }

    public double findMedian() {
        if ((minHeap.size() + maxHeap.size()) == 0) return 0.0;
        double median;
        if ((minHeap.size() + maxHeap.size()) % 2 == 0 ) {
            median = (maxHeap.peek() + minHeap.peek()) / 2.0;
        } else {
            median = minHeap.peek();
        }
        return median;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */