優先隊列【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是可以的。