目錄標題

• • 前言
  • PriorityQueue特點
  • API
  • • 構造
    • 操作API
  • 底層顯示：數組
  • offer(E e)

10年積累的成都網站建設、網站建設經驗，可以快速應對客戶對網站的新想法和需求。提供各種問題對應的解決方案。讓選擇我們的客戶得到更好、更有力的網絡服務。我雖然不認識你，你也不認識我。但先網站設計后付款的網站建設流程，更有色尼免費網站建設讓你可以放心的選擇與我們合作。前言

PriorityQueue是優先隊列，作用是保證每次取出的元素都是隊列中權值最小的，這里涉及到了大小關系，元素大小的評判可以通過元素自身的自然順序（使用默認的比較器），也可以通過構造時傳入的比較器。

Java中PriorityQueue實現了Queue接口，不允許放入null元素；其通過堆實現，具體說是通過完全二叉樹（complete binary tree）實現的小頂堆（任意一個非葉子節點的權值，都不大于其左右子節點的權值），也就意味著可以通過數組來作為PriorityQueue的底層實現。

PriorityQueue特點

1. PriorityQueue是一個無限制的隊列，并且動態增長。默認初始容量’11’可以使用相應構造函數中的initialCapacity參數覆蓋。
2. 它不允許NULL對象。
3. 添加到PriorityQueue的對象必須具有可比性。
4. 默認情況下，優先級隊列的對象按自然順序排序。
5. 比較器可用于隊列中對象的自定義排序。
6. 優先級隊列的頭部是基于自然排序或基于比較器的排序的最小元素。當我們輪詢隊列時，它從隊列中返回頭對象。
7. 如果存在多個具有相同優先級的對象，則它可以隨機輪詢其中任何一個。
8. PriorityQueue 不是線程安全的，所以Java提供了PriorityBlockingQueue（實現BlockingQueue接口）用于Java多線程環境。
9. peek()和element操作是O(1)，add(), offer(), 無參數的remove()以及poll()方法的時間復雜度都是log(N)。

API 構造

PriorityQueue（）：使用默認初始容量（11）構造空隊列，該容量根據其自然順序對其元素進行排序。
PriorityQueue（int initialCapacity）：構造具有指定初始容量的空隊列，該容量根據其自然順序對其元素進行排序。
PriorityQueue（int initialCapacity，Comparator comparator）：構造具有指定初始容量的空隊列，該容量根據指定的比較器對其元素進行排序。

操作API

boolean add（object）：將指定的元素插入此優先級隊列。
boolean offer（object）：將指定的元素插入此優先級隊列。
boolean remove（object）：從此隊列中刪除指定元素的單個實例（如果存在）。
Object poll（）：檢索并刪除此隊列的頭部，如果此隊列為空，則返回null。
Object element（）：檢索但不刪除此隊列的頭部，如果此隊列為空，則返回null。
Object peek（）：檢索但不刪除此隊列的頭部，如果此隊列為空，則返回null。
void clear（）：從此優先級隊列中刪除所有元素。
Comparator comparator（）：返回用于對此隊列中的元素進行排序的比較器，如果此隊列根據其元素的自然順序排序，則返回null。
boolean contains（Object o）：如果此隊列包含指定的元素，則返回true。
int size（）：返回此隊列中的元素數。
Object [] toArray（）：返回包含此隊列中所有元素的數組。

底層顯示：數組

上圖中我們給每個元素按照層序遍歷的方式進行了編號，如果你足夠細心，會發現父節點和子節點的編號是有聯系的，更確切的說父子節點的編號之間有如下關系：

leftNo = parentNo*2+1
rightNo = parentNo*2+2
parentNo = (nodeNo-1)/2

通過上述三個公式，可以輕易計算出某個節點的父節點以及子節點的下標。這也就是為什么可以直接用數組來存儲堆的原因。
PriorityQueue的peek()和element操作是常數時間，add(), offer(), 無參數的remove()以及poll()方法的時間復雜度都是log(N)。

offer(E e)

public boolean offer(E e) {if (e == null)//不允許放入null元素
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);//自動擴容
    size = i + 1;
    if (i == 0)//隊列原來為空，這是插入的第一個元素
        queue[0] = e;
    else
        siftUp(i, e);//調用siftUp函數從下往上調整堆
    return true;
}

private void siftUp(int k, E x) {if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}

private void siftUpComparable(int k, E x) {Comparablekey = (Comparable) x;
        while (k >0) {int parent = (k - 1) >>>1;	//拿到父節點
            Object e = queue[parent];
            if (key.compareTo((E) e) >= 0) //當前元素>父節點 break
                break;
            queue[k] = e; //當前元素<父節點 父節點元素放置在當前位置，k變成當前父節點，繼續下一輪循環，直到當前元素>父節點 break
            k = parent;
        }
        queue[k] = key;//最后把key賦值到正確的位置
    }

當前元素與父節點不斷比較如果比父節點小就交換然后繼續向上比較，否則停止比較的過程

前言：https://blog.csdn.net/hellokitty136/article/details/105831884/
特點/API：https://twotree.blog.csdn.net/article/details/86503464
源碼視頻講解：https://www.bilibili.com/video/BV1tW411j7dL/

你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

分享文章：PriorityQueue詳解-創新互聯
網站路徑：http://vcdvsql.cn/article32/dgogpc.html

成都網站建設公司_創新互聯，為您提供標簽優化、服務器托管、域名注冊、企業建站、電子商務、外貿網站建設

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯