一、基本介紹
1、介紹
PriorityQueue翻譯為優先隊列，“優先”指元素在隊列中按一定的順序（優先級）進行存放，“隊列”指一種先進先出的資料結構。是以PriorityQueue可以實作按照一定的優先級存取元素。
2、用法
從源碼來看PriorityQueue的構造方法：
//預設容量為 11
private static final int DEFAULT_INITIAL_CAPACITY = 11;
//1、無參構造，預設容量和預設排序方法
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
//2、指定容量
public PriorityQueue(int initialCapacity) {
this(initialCapacity, null);
}
//3、指定排序方法
public PriorityQueue(Comparator<? super E> comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator);
}
//4、指定容量和排序方法
public PriorityQueue(int initialCapacity,
Comparator<? super E> comparator) {
// Note: This restriction of at least one is not actually needed,
// but continues for 1.5 compatibility
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
由上可知，在構造PriorityQueue時我們可以指定初始容量和元素在隊列中的排序方法，若不指定，則預設初始容量為11，預設排序方法為将元素從小到大進行排序。
3、最小堆
構造最小堆：
使用無參構造，元素在隊列中預設按照從小到大的順序排列，可保證每次出隊列的元素為隊列中的最小元素。
4、最大堆
将排序方法指定為反序，即元素從大到小排列，可保證每次出隊列的元素為隊列中最大的元素。
5、其他優先級
按照其他優先級規則排序，需要自己實作Comparable接口，重寫compareTo()方法。
Comparable<Integer> comparable = new Comparable<Integer>() {
@Override
public int compareTo(Integer o) {
return 0;
}
};
二、常用方法
以Integer類型為例：
三、相關練習題
【劍指 Offer 40. 最小的k個數】
輸入整數數組 arr ，找出其中最小的 k 個數。例如，輸入4、5、1、6、2、7、3、8這8個數字，則最小的4個數字是1、2、3、4。
示例 1：
輸入：arr = [3,2,1], k = 2
輸出：[1,2] 或者 [2,1]
示例 2：
輸入：arr = [0,1,2,1], k = 1
輸出：[0]
限制：
0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000
【解題思想】
先将k個數放進最大堆，再從第k+1個數開始比較，若其小于大堆頂則加入堆，堆頂出隊列，若大于等于則無作為。
【代碼】
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
int res[] = new int[k];
int len = arr.length;
if(len == 0 || k == 0)
return res;
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
for(int i = 0; i < k; i++){
maxHeap.add(arr[i]);
}
for(int i = k; i < len; i++){
if(arr[i] < maxHeap.peek()){
maxHeap.add(arr[i]);
maxHeap.poll();
}
}
for(int i = 0; i < k; i++){
res[i] = maxHeap.poll();
}
return res;
}
}
時間複雜度：O（nlogn）