PriorityQueues优先队列

优先队列

优先队列（priority queue）是计算机科学中的一类抽象数据类型。优先队列中的每个元素都有各自的优先级，优先级最高的元素最先得到服务；优先级相同的元素按照其在优先队列中的顺序得到服务。优先队列通常使用“堆”（heap）实现。

优先队列至少需要支持下述操作：

• 插入带优先级的元素（insert_with_priority）

• 取出具有最高优先级的元素（pull_highest_priority_element）

• 查看最高优先级的元素（peek）：O(1) 时间复杂度

其它可选的操作：

• 检查优先级高的一批元素

• 清空优先队列

• 批插入一批元素

• 合并多个优先队列

• 调整一个元素的优先级

怎样理解优先队列？

举个例子。一家诊所，只有一个医生为病人看病。每个病人依据他们的病情，都会有一个看病的优先级。抽象出一个队列，当病人进入队列时，代表需要等待医生空闲；出队列时，病人接受治疗。一个病人患了感冒，优先级较低，让他在队列中等待，待医生空闲时再为他治疗；接下来，另一位病人前来看病，这位病人伤得不轻，病人头上插着斧头正血流不止，优先级较高，会让他先出队列进行治疗。

在java中的优先队列是一个最小堆，我们可以通过comparator将其变成最大堆

例题

Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2

Output: [1,2]

Example 2:

Input: nums = [1], k = 1

Output: [1]

Constraints:

1 <= nums.length <= 105

-104 <= nums[i] <= 104

k is in the range [1, the number of unique elements in the array].

It is guaranteed that the answer is unique.

Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

来源：力扣（LeetCode）

链接：https://leetcode.cn/problems/top-k-frequent-elements

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {public int[] topKFrequent(int[] nums, int k) {//key:num   value:frequencyHashMap<Integer,Integer> map = new HashMap<>();//int[0]:num    int[1]:frequencyPriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {return o2[1] - o1[1];}});//iterate through nums and insert k-v into mapfor(int num : nums) {map.put(num,map.getOrDefault(num,0) + 1);}for (Map.Entry<Integer, Integer> entry : map.entrySet()) {Integer key = entry.getKey();Integer value = entry.getValue();pq.add(new int[]{key,value});}int[] ans = new int[k];for (int i = 0;i < k;i++) {ans[i] = pq.poll()[0];}return ans;}
}