Java集合框架之PriorityQueue優先權佇列

這篇文章為大家帶來了關於java的相關知識，其中主要介紹了關於PriorityQueue優先權隊列的相關知識，Java集合框架中提供了PriorityQueue和PriorityBlockingQueue兩種類型的優先級隊列，PriorityQueue是線程不安全的，PriorityBlockingQueue是線程安全的，下面一起來看一下，希望對大家有幫助。

推薦學習：《java影片教學》

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中常見的幾種建構方式

，其他的大家可以參考幫助文件。

建構器#PriorityQueue()預設容量是11PriorityQueue(int initialCapacity)初始容量為initialCapacityPriorityQueue(Collection extends E> c)預設初始容量的優先權佇列#建立一個##

 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、插入/刪除/取得優先順序最高的元素

功能介紹
建立一個空的優先權佇列，
建立一個	的優先權佇列，注意：initialCapacity不能小於1，否則會拋IllegalArgumentException異常
用一個集合來建立優先權佇列
PriorityQueue(Comparator comparator)建立具有	，並根據指定的比較器對其元素進行比較
#PriorityQueue(int initialCapacity, Comparator  comparator)	初始容量為 initialCapacity的優先權佇列<strong></strong>，根據指定的比較器對其元素進行比較 注意： initialCapacity不能小於1，否則會拋IllegalArgumentException異常

##函數名boolean offer(E e) 間複雜度，注意：空間不夠時候會進行擴容E peek()## 取得優先順序最高的元素，如果優先權佇列為空，則傳回nullE poll()移除優先權最高的元素並返回，如果優先權佇列為空，傳回nullint size()取得有效元素的數量void clear()boolean 推薦學習：《java影片教學

功能介紹
插入元素e，插入成功傳回true，如果e物件為空，拋出NullPointerException異常，時
清空
isEmty() 偵測優先權佇列是否為空，為空返回true

》

以上是Java集合框架之PriorityQueue優先權佇列的詳細內容。更多資訊請關注PHP中文網其他相關文章！