1. 場(chǎng)景引入

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

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

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

2. PriorityQueue 介紹

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

3. 知識(shí)點(diǎn)

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

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

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

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

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

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

如何使 PriorityQueue 的底層是一個(gè)大根堆？

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

4. 常用方法

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

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

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

• 示例二： 入隊(duì)列

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

• 示例三： 得到隊(duì)首元素

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

• 示例四： 出隊(duì)列

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

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

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

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

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

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

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

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àn)閮?yōu)先級(jí)隊(duì)列的底層默認(rèn)是一個(gè)小根堆，它存入元素時(shí)是需要進(jìn)行比較對(duì)象的大小的。

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

此時(shí)我們的 comparator 默認(rèn)是 null，我們?cè)俎D(zhuǎn)到 offer 方法的定義看看

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

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

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

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

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

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

6.1 思路

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

6.2 代碼實(shí)現(xiàn)

// 定義的某個(gè)要比較類型的比較器
class IntegerComparator implements Comparator<Integer>{
    @Override
    public int compare(Integer o1,Integer o2){
        // 如果第二個(gè)元素-第一個(gè)元素就是大根堆的實(shí)現(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)使用了一個(gè)匿名的內(nèi)部類的方式去創(chuàng)建大根堆

總結(jié)

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