优先级队列

优先级队列，这个数据结构可以理解为一个箱子，给定一个比较的规则，然后比较的比较有限的元素，会沉的比较下面，当要取出一个元素的时候，最上面的元素就会率先被取出来。

举个例子。

public static void main(String[] args) {PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(((o1, o2) -> o2 - o1));priorityQueue.offer(0);priorityQueue.offer(1);priorityQueue.offer(2);priorityQueue.offer(3);priorityQueue.offer(4);priorityQueue.offer(5);while (!priorityQueue.isEmpty()) {System.out.println(priorityQueue.poll());}
}

这段代码中，比较函数的实现是(o1, o2) -> o2 - o1，就说明，o1和o2对比，值比较小的那个更要下沉，所以，当挨个取出优先级队列里面的元素的时候，比较先出来的一定是元素比较小的那个，因为元素大的都沉在底下。

详细的说一下Comparator接口的compare方法，参数为(T o1, T o2)，当返回正数的时候，证明o1要比o2优先，当返回负数的时候证明o2要比o1优先，0的时候就是一样的嘛，我们可以这么记忆，我们用前面的o1减去后面的o2，都是正数了，那么一定前面的大喽。

这种实现的方式其实就是堆，如果你学过堆排序，就知道，这其实就是一个最小堆。

因为这种特性，凡事说，求第K个，或者前K个的问题，基本上就可以用优先级队列，也就是堆这种数据结构来搞定。

如果求前K大的元素，我们只需要构建一个K大小的最小堆，就是堆顶的元素是整个堆最小的元素的堆，然后从K+1个元素开始和堆顶的元素比，如果比整个堆最小的元素还小，就肯定不是前K大的，但如果比堆顶的要大，那么就加入这个堆，从新调整为一个最小堆，再把堆顶的元素poll掉，保证堆的长度为K。

一道题

前K个高频单词

给一非空的单词列表，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。

我们就可以用一个hashmap统计单词出现的次数，然后构建一个k大小的堆，优先级是频次越高的越优先，频次一样的，单词首字母越靠前的越优先（String重写的比较方法，本来就是这么实现的），然后挨个取出优先级队列里面的数据，这时候是从不优先的到优先的，逆转就是我们要的结果。

public static List<String> topKFrequent(String[] words, int k) {Map<String, Integer> map = new HashMap<>();for (String word : words) {map.put(word, map.getOrDefault(word, 0) + 1);}PriorityQueue<Map.Entry<String, Integer>> priorityQueue = new PriorityQueue<>(((o1, o2) -> o1.getValue().equals(o2.getValue()) ? o2.getKey().compareTo(o1.getKey()) : o1.getValue() - o2.getValue()));for (Map.Entry<String, Integer> entry : map.entrySet()) {priorityQueue.offer(entry);if (priorityQueue.size() > k) {priorityQueue.poll();}}List<String> res = new LinkedList<>();while (!priorityQueue.isEmpty()) {res.add(priorityQueue.poll().getKey());}Collections.reverse(res);return res;
}

内推

需要内推阿里巴巴的同学，关注博客后私信内推，即可获得内推资格。