优先队列【Java：PriorityQueue】

PriorityQueue

• • • • 介绍
      • 方法
      • 构造对象（重点）
      • 解决leetcode问题
      • 注意事项

介绍

• 本篇文章介绍Java中的PriorityQueue类
• 首先说一下概念，PriorityQueue会维护一个堆（大顶堆、小顶堆），无论进行怎样的插入、删除操作，通过其内部的机制，将在这些动态的操作下保证其堆顶是最大值或最小值。
• 通过public class PriorityQueue extends AbstractQueue implements Serializable，我们知道：PriorityQueue类实现的接口和继承父类有【Serializable ， Iterable ， Collection ， Queue】，因为AbstractQueue接口继承了【Iterable ， Collection ， Queue】

方法

• PriorityQueue类的方法与Queue的方法差不多，主要有以下方法：

清空队列

void clear()

是否包含指定元素

boolean contains(Object o)

将指定元素插入队列，注意PriorityQueue会进行排序，即插入元素后，队列仍就是有序的

boolean offer(E e)

获得队首元素，但不删除

E peek()

将队首元素从队列中删除，并返回旧元素

E poll()

转换为数组

Object[] toArray()

…

构造对象（重点）

• PriorityQueue与Queue不同的是构造对象的时候，我们需要传入一个比较器对象，并实现比较器的接口方法compare。

PriorityQueue<Integer> queue=new PriorityQueue<Integer>(new Comparator<Integer>(){
            public int compare(Integer e1,Integer e2){
                return e2-e1;
            }
        });
           

解决leetcode问题

class Solution {
    public int findKthLargest(int[] nums, int k) {
	    //创建优先队列
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>(){
        	//设置排序规则
            public int compare(Integer m,Integer n){
                return n-m;
            }
        });
        //将数组中的元素一个一个插入至优先队列中，优先队列保证其有序性
        for(int i : nums){
            queue.offer(i);
        }
        //将优先队列前k个元素删除
        for(int i=0;i<k-1;i++){
            queue.poll();
        }
        //获取第k个元素，因为其经过排序，因此该元素在数组中也是第k大的
        return queue.poll();
    }
}
           

注意事项

• PriorityQueue与TreeSet有亿点点像，但Set集合是不允许存储重复元素的，而ProrityQueue是可以的。