简述

  1. 优先队列不像普通队列是按照插入顺序先入先出的，它是按照元素的大小进行实时排列的，值小的先出，值大的后出。例如：优先队列[1,3]，此时插入一个2，优先队列变为[1,2,3]。
  2. 优先队列的底层数据结构是二叉堆的小根堆形式，默认情况下堆顶每次都保留最小值，并在插入元素后动态维护最小值。
  3. java中优先队列是以小根堆为底层，也就是升序排列。要想实现大根堆（降序排列），可以利用匿名内部类Comparator ；也可以让插入的元素先取负再插入（元素越大，其负数就越小），之后读取的时候再取负还原即可

优先队列在做题时的优势就是其可以实时维护最小值，即将元素按升序排列插入到它该去的位置。

实例化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 1.构造一个小根堆（默认）
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

//2.构造一个大根堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>(){
	@Override
	public int compare(Integer o1, Integer o2) {                
		return o2-o1;
	}
});

//最好用lambda表达式来代替匿名内部类实现大根堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1,o2) -> o2-o1);//lambda表达式

API

  1. offer(E e) 将指定元素插入此优先队列，失败返回false
  2. add(E e) 将指定元素插入此优先队列，失败抛异常
  3. poll() 获取并移除第一个元素(第一个元素为最小元素)
  4. remove(Object o) 移除指定元素
  5. peek() 获取第一个元素，及最小或最大元素
  6. size() 返回元素个数
  7. clear() 清空
  8. contains(Object o) 如果包含指定元素返回true。

应用

一般用来解决 第K个XXX元素 这类的问题

例：数组中的第K个最大元素
题目详见 https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int count = 0;
        for(int i = 0; i < nums.length; i++){
            // 先将优先队列填满至K个元素
            if(count < k){
                pq.offer(nums[i]);
                count++;
                continue;
            }
            // 优先队列大小达到K后，依次进行判断，使优先队列中始终储存前K大的元素
            if(nums[i] > pq.peek()){
                pq.poll();
                pq.offer(nums[i]);
            }
        }
        return pq.peek();
    }
}