Java集合框架之PriorityQueue優先順序佇列

推薦學習：《》

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue兩種型別的優先順序佇列，PriorityQueue是執行緒不安全的，PriorityBlockingQueue是執行緒安全的，本文主要介紹PriorityQueue

priorityQueue在Java集合框架中的關係如下：

一、使用PriorityQueue的注意點

1. 使用時必須匯入PriorityQueue所在的包，即：

import java.util.PriorityQueue

2. PriorityQueue中放置的元素必須要能夠比較大小，不能插入無法比較大小的物件，否則會丟擲
ClassCastException異常

3. 不能插入null物件，否則會丟擲NullPointerException

4. 沒有容量限制，可以插入任意多個元素，其內部可以自動擴容

5. 插入和刪除元素的時間複雜度為log以2為底的n

6. PriorityQueue底層使用了堆資料結構

7. PriorityQueue預設情況下是小堆---即每次獲取到的元素都是最小的元素（想要變成大堆，需要我們重新比較方法、預設的比較方法是Comparable介面中的compareTo方法）

二、PriorityQueue常用介面介紹

1. 優先順序佇列的構造

此處只是列出了PriorityQueue中常見的幾種構造方式，其他的大家可以參考幫助檔案。

2、PriorityQueue中對元素的比較

看完了構造方法，我們重新來思考一個問題

優先順序佇列是如何實現有序的呢？因為優先順序佇列就是藉助小根堆來實現的

在實現小根堆的過程我們知道這其中一定發生了元素的比較，所以PriorityQueue中的元素必須要能夠比較大小，那麼PriorityQueue是如何進行元素的比較呢？

PriorityQueue採用了：
Comparble和Comparator兩種方式。

1. Comparble是預設的內部比較方式，如果使用者插入自定義型別物件時，該類物件必須要實現Comparble介面，並覆寫compareTo方法

2. 使用者也可以選擇使用比較器物件，如果使用者插入自定義型別物件時，必須要提供一個比較器類，讓該類實現Comparator介面並覆寫compare方法。

我們看到這裡程式報錯了，為什麼呢？因為我們插入的Child物件是不可比較的（即沒有實現Comparable介面又沒有采用自定義的比較器）

可以看到

即我們採用了預設的比較方法Comparable介面中的compareTo方法

此時我們再次看一下報錯資訊

看來是在往PriorityQueue中插入元素的時候出現了問題

那麼我們開啟PriorityQueue的原始碼看一下（下面是PriorityQueue中offer方法的原始碼）

再看看shiftUp的原始碼

繼續點進去siftUpComparable

此時再回過頭來看看我們放到PriorityQueue中的Child物件，他即沒有自定義比較器又沒有實現Comparable介面，當然報錯呀！

那麼好吧我們在Child類中實現Comparable介面，按年齡進行比較

import java.util.PriorityQueue;
class Child implements Comparable<Child>{
    int age;
    String name;

    public Child(int age, String name) {
        this.age = age;
        this.name = name;
    }

    @Override
    public int compareTo(Child o) {
        return this.age - o.age;  // 預設實現小根堆
    }

    @Override
    public String toString() {
        return "Child{" +
                "age=" + age +
                ", name='" + name + '\'' +
                '}';
    }
}
public class TestPriorityQueue {
    public static void main(String[] args) {
        PriorityQueue<Child> priorityQueue = new PriorityQueue<>();

        priorityQueue.offer(new Child(12, "小亮"));
        priorityQueue.offer(new Child(11, "小紅"));
        priorityQueue.offer(new Child(8, "小強"));
        System.out.println(priorityQueue);
    }
}

如果要實現大根堆，也好辦

上面我們是實現了Compable介面，那麼如果我們自定義一個年齡比較器呢？

class Child {
    int age;
    String name;

    public Child(int age, String name) {
        this.age = age;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Child{" +
                "age=" + age +
                ", name='" + name + '\'' +
                '}';
    }
}
class AgeComparator implements Comparator<Child> {

    @Override
    public int compare(Child o1, Child o2) {
        return o1.age - o2.age; // 實現小根堆
        // return o2.ae - o1.age 實現大根堆
    }
}
public class TestPriorityQueue {
    public static void main(String[] args) {
        AgeComparator ageComparator = new AgeComparator();
        // 建立具有預設初始容量的 PriorityQueue ，並根據指定的比較器對其元素進行排序。
        PriorityQueue<Child> priorityQueue = new PriorityQueue<>(ageComparator);
        // 可以看到這裡我的Child物件雖然沒有實現Comparable介面，但因為我們對Child物件自定義了一個年齡比較器，所以插入元素不會報錯
        priorityQueue.offer(new Child(12, "小亮"));
        priorityQueue.offer(new Child(11, "小紅"));
        priorityQueue.offer(new Child(8, "小強"));
        System.out.println(priorityQueue);
    }
}

3、插入/刪除/獲取優先順序最高的元素

推薦學習：《》

以上就是Java集合框架之PriorityQueue優先順序佇列的詳細內容，更多請關注TW511.COM其它相關文章！