1. 場景引入

我們知道，Queue是一個先進(jìn)先出（FIFO）的隊列。

在很多應(yīng)用中，我們通常需要按照優(yōu)先情況對待處理對象進(jìn)行處理，比如首先處理優(yōu)先級最高的對象，然后處理次高的對象。最簡單的一個例子就是，在手機(jī)上玩游戲時，如果有來電，那么系統(tǒng)應(yīng)該優(yōu)先處理進(jìn)來的電話。

這個時候，我們發(fā)現(xiàn)，要實現(xiàn)上述的操作，用Queue就不行了，因為Queue會嚴(yán)格按 FIFO 的原則取出隊首元素。故有了我們需要的優(yōu)先隊列：PriorityQueue。

2. PriorityQueue 介紹

Java 中 PriorityQueue 繼承了 Queue 接口，它的底層是一個堆。

3. 知識點

PriorityQueue 的底層是一個數(shù)組

我們可以轉(zhuǎn)到它的定義，可以看到它的底層定義是一個數(shù)組。為了知道這個數(shù)組的初始大小有多大

再通過它的參構(gòu)造方法轉(zhuǎn)到定義，又可以看到

再點擊 this，轉(zhuǎn)到其定義，我們發(fā)現(xiàn)又跳到了一個含兩個參數(shù)的構(gòu)造方法

又在 PriorityQueue 的定義中 DEFAULT_INITIAL_CAPACITY = 11，即 initialCapacity = 11，所以我們可以知道數(shù)組的初始大小為11

PriorityQueue 的底層默認(rèn)是一個小根堆

如何使 PriorityQueue 的底層是一個大根堆？

引用上圖 PriorityQueue 的含參定義，我們知道第一個參數(shù)代表數(shù)組的大小，而第二個參數(shù)就一個比較器，傳給他的就是比較的方法，通過給他傳入大根堆的比較方式，我們就可以使 PriorityQueue 的底層變成大根堆

4. 常用方法

注意： 下面的示例都是一份代碼分開拿出來的，上下其實是有邏輯關(guān)系的

• 示例一： 用 Priority Queue 創(chuàng)建一個優(yōu)先級隊列

PriorityQueue<Integer> queue=new PriorityQueue<>();

• 示例二： 入隊列

queue.offer(10);
queue.offer(2);
queue.offer(5);

• 示例三： 得到隊首元素

System.out.println(queue.peek());
// 結(jié)果為：2

• 示例四： 出隊列

System.out.println(queue.poll());
// 結(jié)果為：2

• 示例五： 返回集合中元素個數(shù)

System.out.println(queue.size());
// 結(jié)果為：2

5. 優(yōu)先級隊列插入元素的細(xì)節(jié)問題

當(dāng)我們使用優(yōu)先級隊列的時候，插入元素其實有個前提：

插入的元素不能是 null 或者元素之間必須能夠進(jìn)行比較

而基本的包裝類類型都可以進(jìn)行比較，如：Integer、Double、Float。但是對于我們自定義的類型，其實就可能不能比較，就如下面這個類當(dāng)我們使用優(yōu)先級隊列對它的對象進(jìn)行插入時，其實會報錯

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));
    }
}

這是因為優(yōu)先級隊列的底層默認(rèn)是一個小根堆，它存入元素時是需要進(jìn)行比較對象的大小的。

我們可以轉(zhuǎn)到 PriorityQueue 的無參構(gòu)造方法的定義看看

此時我們的 comparator 默認(rèn)是 null，我們再轉(zhuǎn)到 offer 方法的定義看看

好像并沒有什么異常，但是由于我 插入第二個元素時，i 不為0，所以要進(jìn)行 siftUp 方法，我們轉(zhuǎn)到它的定義

由于我們知道 comparator 為 null，那么則要進(jìn)行 siftUpComparable 方法，繼續(xù)轉(zhuǎn)到它的定義

我們發(fā)現(xiàn)，創(chuàng)建的 Student 的對象，被強(qiáng)轉(zhuǎn)為了 Comparable<? super E>，并且還調(diào)用了 compareTo 方法。

如果大家有看過我寫的 解析 Java 的多態(tài)、抽象類和接口 和 Java 對象的比較 這兩篇文章，那我就有講到 compareTo 這個方法。這個方法是 Comparable 的一個抽象方法，定義的是比較對象大小的一個規(guī)則。

因此為了解決這個問題，我們就可以使用和 Comparable 或 Comparator 接口相關(guān)的知識

6. PriorityQueue 大根堆的創(chuàng)建方式

6.1 思路

這里便不對源碼做具體分析，我們?nèi)绻?PriorityQueue 創(chuàng)建出的是一個大根堆，只需要對具體類型寫一個比較器即可

6.2 代碼實現(xiàn)

// 定義的某個要比較類型的比較器
class IntegerComparator implements Comparator<Integer>{
    @Override
    public int compare(Integer o1,Integer o2){
        // 如果第二個元素-第一個元素就是大根堆的實現(xiàn)方式，反之則為小根堆的創(chuàng)建方式，可以從源碼去了解
        return o2-o1;
    }
}
public class TestDemo{
    public static void main(String[] args){
        PriorityQueue<Integer> maxHeap=new PriorityQueue<>(IntegerComparator);
    }
}

6.3 使用匿名內(nèi)部類

上述代碼也可以寫成

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;
            }
        })
    }
}

這相當(dāng)使用了一個匿名的內(nèi)部類的方式去創(chuàng)建大根堆

總結(jié)

以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。

最新評論