Java优先级队列（概念+例题）

优先级队列的Java实现是一种特殊的队列，其中元素的排序由其自然排序原则确定(默认最小堆)，也可以根据创建期间提供的Comparator进行定制。我们在构造过程中调用的构造函数决定要与优先级队列一起使用的排序原则。与不允许使用null元素的Queue 不同，但是某些实现（例如linkedList）也不禁止插入null元素。但是，PriorityQueue 根本不允许空元素。如果优先级队列是根据自然顺序构造的，则任何不可比较的元素插入都将引发ClassCastException。

它被声明为无限制的并且基于优先级堆。尽管队列的大小被称为无限制，但内部具有确定阵列大小的能力。插入元素时，此大小会自动增长。但是，没有详细说明增大尺寸的原理。

​//基于最小堆实现
 PriorityQueuequeue=new PriorityQueue<>();
        int []arr={5,4,3,2,1};
        for(int i:arr)
        {
            queue.offer(i);
        }
        for(int i:arr)
        {
            System.out.print(queue.poll());
        }
//输出结果：1，2，3，4，5

​

//基于最大堆实现
 PriorityQueuequeue=new PriorityQueue<>(new Comparator() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        int []arr={1,2,3,4,5};
        for(int i:arr)
        {
            queue.offer(i);
        }
        for(int i:arr)
        {
            System.out.print(queue.poll());
        }
//输出结果：5，4，3，2，1

//优先级队列的主要作用就是用来动态排序
class Solution {
    public int lastStoneWeight(int[] stones) {

Queuequeue=new PriorityQueue<>(new Comparator()
{
    @Override
    public int compare(Integer o1,Integer o2)//使用Comparator自定义实现降序操作
    {
        return o2-o1;
    }
});
for(int i:stones)
{
    queue.offer(i);//构建大根堆
}
while(queue.size()>1)
{
    int y=queue.poll();  //把当前堆顶元素出堆
    int x=queue.poll();
    if(x==y)
    {
        continue;
    }
    else
    {
        int z=y-x;
        queue.offer(z);
    }
}return queue.isEmpty() ? 0 : queue.poll();
    }
}

class Solution {
       private class Freq implements Comparable//用类把不同数据联系起来
        { 
            private int key;
            private int times;
            public Freq(int key,int times)//构造函数
            {
                this.key=key;
                this.times=times;
            }
        
        @Override//最小堆的比较器
        public int compareTo(Freq o)
        {
            return this.times-o.times;
        }
        }
        public int []topKFrequent(int []nums,int k)
        {
            int []ret=new int [k];
            Mapmap=new HashMap<>();//创建一个哈希表
            for(int i:nums)
            {
                if(map.containsKey(i))
                {
                    map.put(i,map.get(i)+1);//存储元素出现的次数
                }
                else
                {
                    map.put(i,1);
                }
            }
            
            Queuequeue=new PriorityQueue<>();
            for(Map.Entryentry:map.entrySet())//遍历哈希表，把value元素以最小根的形式存储，
            {
                if(queue.size() 
 总结 
注意1：该队列是用数组实现，但是数组大小可以动态增加，容量无限。
 
注意2：队列的实现不是同步的。不是线程安全的。如果多个线程中的任意线程从结构上修改了列表， 则这些线程不应同时访问 PriorityQueue实例。保证线程安全可以使用PriorityBlockingQueue 类。
 
注意3：不允许使用 null 元素。
 
注意4：插入方法（offer()、poll()、remove() 、add() 方法）时间复杂度为O(log(n)) ；
 remove(Object) 和 contains(Object) 时间复杂度为O(n)；
 检索方法（peek、element 和 size）时间复杂度为常量。
 
注意5：方法iterator()中提供的迭代器并不保证以有序的方式遍历优先级队列中的元素。（原因可参考PriorityQueue的内部实现）
 如果需要按顺序遍历，可用Arrays.sort(pq.toArray())。
 
注意6：可以在构造函数中指定如何排序。如：
 PriorityQueue()
           使用默认的初始容量（11）创建一个 PriorityQueue，并根据其自然顺序来排序其元素（使用 Comparable）。
 PriorityQueue(int initialCapacity)
           使用指定的初始容量创建一个 PriorityQueue，并根据其自然顺序来排序其元素（使用 Comparable）。
 PriorityQueue(int initialCapacity, Comparator comparator)
           使用指定的初始容量创建一个 PriorityQueue，并根据指定的比较器comparator来排序其元素。
 
注意7：此类及其迭代器实现了 Collection 和 Iterator 接口的所有可选 方法。
 
PriorityQueue对元素采用的是堆排序，头是按指定排序方式的最小元素。堆排序只能保证根是最大（最小），整个堆并不是有序的。
 方法iterator()中提供的迭代器可能只是对整个数组的依次遍历。也就只能保证数组的第一个元素是最小的。