PriorityQueue詳解-創(chuàng)新互聯(lián)

目錄標(biāo)題
    • 前言
    • PriorityQueue特點(diǎn)
    • API
      • 構(gòu)造
      • 操作API
    • 底層顯示：數(shù)組
    • offer(E e)

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

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

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

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

PriorityQueue（）：使用默認(rèn)初始容量（11）構(gòu)造空隊(duì)列，該容量根據(jù)其自然順序?qū)ζ湓剡M(jìn)行排序。
PriorityQueue（int initialCapacity）：構(gòu)造具有指定初始容量的空隊(duì)列，該容量根據(jù)其自然順序?qū)ζ湓剡M(jìn)行排序。
PriorityQueue（int initialCapacity，Comparator comparator）：構(gòu)造具有指定初始容量的空隊(duì)列，該容量根據(jù)指定的比較器對(duì)其元素進(jìn)行排序。

操作API

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

底層顯示：數(shù)組

在這里插入圖片描述
在這里插入圖片描述
上圖中我們給每個(gè)元素按照層序遍歷的方式進(jìn)行了編號(hào)，如果你足夠細(xì)心，會(huì)發(fā)現(xiàn)父節(jié)點(diǎn)和子節(jié)點(diǎn)的編號(hào)是有聯(lián)系的，更確切的說(shuō)父子節(jié)點(diǎn)的編號(hào)之間有如下關(guān)系：

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

通過(guò)上述三個(gè)公式，可以輕易計(jì)算出某個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)以及子節(jié)點(diǎn)的下標(biāo)。這也就是為什么可以直接用數(shù)組來(lái)存儲(chǔ)堆的原因。
PriorityQueue的peek()和element操作是常數(shù)時(shí)間，add(), offer(), 無(wú)參數(shù)的remove()以及poll()方法的時(shí)間復(fù)雜度都是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);//自動(dòng)擴(kuò)容
    size = i + 1;
    if (i == 0)//隊(duì)列原來(lái)為空，這是插入的第一個(gè)元素
        queue[0] = e;
    else
        siftUp(i, e);//調(diào)用siftUp函數(shù)從下往上調(diào)整堆
    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é)點(diǎn)
            Object e = queue[parent];
            if (key.compareTo((E) e) >= 0) //當(dāng)前元素>父節(jié)點(diǎn) break
                break;
            queue[k] = e; //當(dāng)前元素<父節(jié)點(diǎn) 父節(jié)點(diǎn)元素放置在當(dāng)前位置，k變成當(dāng)前父節(jié)點(diǎn)，繼續(xù)下一輪循環(huán)，直到當(dāng)前元素>父節(jié)點(diǎn) break
            k = parent;
        }
        queue[k] = key;//最后把key賦值到正確的位置
    }

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

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

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

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

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

廣告

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

網(wǎng)站建設(shè)網(wǎng)站維護(hù)公司