目錄標題

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

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

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

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

PriorityQueue特點

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

API 構造

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

操作API

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

底層顯示：數(shù)組

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

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

通過上述三個公式，可以輕易計算出某個節(jié)點的父節(jié)點以及子節(jié)點的下標。這也就是為什么可以直接用數(shù)組來存儲堆的原因。
PriorityQueue的peek()和element操作是常數(shù)時間，add(), offer(), 無參數(shù)的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函數(shù)從下往上調整堆
    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;	//拿到父節(jié)點
            Object e = queue[parent];
            if (key.compareTo((E) e) >= 0) //當前元素>父節(jié)點 break
                break;
            queue[k] = e; //當前元素<父節(jié)點 父節(jié)點元素放置在當前位置，k變成當前父節(jié)點，繼續(xù)下一輪循環(huán)，直到當前元素>父節(jié)點 break
            k = parent;
        }
        queue[k] = key;//最后把key賦值到正確的位置
    }

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

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

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

分享文章：PriorityQueue詳解-創(chuàng)新互聯(lián)
網(wǎng)站路徑：http://chinadenli.net/article32/dgogpc.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供標簽優(yōu)化、服務器托管、域名注冊、企業(yè)建站、電子商務、外貿(mào)網(wǎng)站建設

廣告

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