文章目錄
- 1. 場景引入
- 2. PriorityQueue 介紹
- 3. 知識點
- 4. 常用方法
- 5. 優先級佇列插入元素的細節問題
- 6. PriorityQueue 大根堆的創建方式
- 6.1 思路
- 6.2 代碼實作
- 6.3 使用匿名內部類
1. 場景引入
我們知道，Queue是一個先進先出（FIFO）的佇列，
在很多應用中，我們通常需要按照優先情況對待處理物件進行處理，比如首先處理優先級最高的物件，然后處理次高的物件，最簡單的一個例子就是，在手機上玩游戲時，如果有來電，那么系統應該優先處理進來的電話，
這個時候，我們發現，要實作上述的操作，用Queue就不行了，因為Queue會嚴格按 FIFO 的原則取出隊首元素，故有了我們需要的優先佇列：PriorityQueue，
2. PriorityQueue 介紹
Java 中 PriorityQueue 繼承了 Queue 介面，它的底層是一個堆，
3. 知識點
-
PriorityQueue的底層是一個陣列- 我們可以轉到它的定義，可以看到它的底層定義是一個陣列，為了知道這個陣列的初始大小有多大
- 再通過它的參構造方法轉到定義，又可以看到
- 再點擊 this，轉到其定義，我們發現又跳到了一個含兩個引數的構造方法
- 又在
PriorityQueue的定義中DEFAULT_INITIAL_CAPACITY = 11，即initialCapacity = 11，所以我們可以知道陣列的初始大小為11
- 我們可以轉到它的定義，可以看到它的底層定義是一個陣列，為了知道這個陣列的初始大小有多大
-
PriorityQueue的底層默認是一個小根堆 -
如何使
PriorityQueue的底層是一個大根堆？- 參考上圖
PriorityQueue的含參定義，我們知道第一個引數代表陣列的大小，而第二個引數就一個比較器，傳給他的就是比較的方法，通過給他傳入大根堆的比較方式，我們就可以使PriorityQueue的底層變成大根堆
- 參考上圖
4. 常用方法
| 方法 | 描述 |
|---|---|
boolean offer(E e) | 入佇列 |
E poll() | 出佇列 |
E peek() | 得到隊首元素 |
int size() | 回傳集合中的元素個數 |
注意： 下面的示例都是一份代碼分開拿出來的，上下其實是有邏輯關系的
示例一： 用 Priority Queue 創建一個優先級佇列
PriorityQueue<Integer> queue=new PriorityQueue<>();
示例二： 入佇列
queue.offer(10);
queue.offer(2);
queue.offer(5);
示例三： 得到隊首元素
System.out.println(queue.peek());
// 結果為：2
示例四： 出佇列
System.out.println(queue.poll());
// 結果為：2
示例五： 回傳集合中元素個數
System.out.println(queue.size());
// 結果為：2
5. 優先級佇列插入元素的細節問題
當我們使用優先級佇列的時候，插入元素其實有個前提：
插入的元素不能是 null 或者元素之間必須能夠進行比較
而基本的包裝型別別都可以進行比較，如：Integer、Double、Float，但是對于我們自定義的型別，其實就可能不能比較，就如下面這個類當我們使用優先級佇列對它的物件進行插入時，其實會報錯
class Student{
private String name;
private int age;
public Student(String name, int age, double score) {
this.name = name;
this.age = age;
}
}
public class TestDemo{
public static void main(String[] args){
PriorityQueue<Student> queue=new PriorityQueue<>();
queue.offer(new Student("Tom",18));
queue.offer(new Student("Hen",34));
}
}
這是因為優先級佇列的底層默認是一個小根堆，它存入元素時是需要進行比較物件的大小的，
我們可以轉到 PriorityQueue 的無參構造方法的定義看看
此時我們的 comparator 默認是 null，我們再轉到 offer 方法的定義看看
好像并沒有什么例外，但是由于我插入第二個元素時，i 不為0，所以要進行 siftUp 方法，我們轉到它的定義
由于我們知道 comparator 為 null，那么則要進行 siftUpComparable 方法，繼續轉到它的定義
我們發現，創建的 Student 的物件，被強轉為了 Comparable<? super E>，并且還呼叫了 compareTo 方法，如果大家有看過我寫的 決議 Java 的多型、抽象類和介面 和 Java 物件的比較 這兩篇文章，那我就有講到 compareTo 這個方法，這個方法是 Comparable 的一個抽象方法，定義的是比較物件大小的一個規則，
因此為了解決這個問題，我們就可以使用和 Comparable 或 Comparator 介面相關的知識
6. PriorityQueue 大根堆的創建方式
6.1 思路
這里便不對原始碼做具體分析，我們如果要 PriorityQueue 創建出的是一個大根堆，只需要對具體型別寫一個比較器即可
6.2 代碼實作
// 定義的某個要比較型別的比較器
class IntegerComparator implements Comparator<Integer>{
@Override
public int compare(Integer o1,Integer o2){
// 如果第二個元素-第一個元素就是大根堆的實作方式，反之則為小根堆的創建方式，可以從原始碼去了解
return o2-o1;
}
}
public class TestDemo{
public static void main(String[] args){
PriorityQueue<Integer> maxHeap=new PriorityQueue<>(IntegerComparator);
}
}
6.3 使用匿名內部類
上述代碼也可以寫成
public class TestDemo{
public static void main(String[] args){
PriorityQueue<Integer> maxHeap=new PriorityQueue<>(new Comparator<Integer>(){
@Override
public int compare(Integer o1,Integer o2){
return o2-o1;
}
})
}
}
這相當使用了一個匿名的內部類的方式去創建大根堆
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/353379.html
標籤：java