PriorityQueue是優(yōu)先隊(duì)列,作用是保證每次取出的元素都是隊(duì)列中權(quán)值最小的,這里涉及到了大小關(guān)系,元素大小的評判可以通過元素自身的自然順序(使用默認(rèn)的比較器),也可以通過構(gòu)造時傳入的比較器。
Java中PriorityQueue實(shí)現(xiàn)了Queue接口,不允許放入null元素;其通過堆實(shí)現(xiàn),具體說是通過完全二叉樹(complete binary tree)實(shí)現(xiàn)的小頂堆(任意一個非葉子節(jié)點(diǎn)的權(quán)值,都不大于其左右子節(jié)點(diǎn)的權(quán)值),也就意味著可以通過數(shù)組來作為PriorityQueue的底層實(shí)現(xiàn)。
PriorityQueue特點(diǎn)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ù)指定的比較器對其元素進(jìn)行排序。
boolean add(object)
:將指定的元素插入此優(yōu)先級隊(duì)列。boolean offer(object)
:將指定的元素插入此優(yōu)先級隊(duì)列。boolean remove(object)
:從此隊(duì)列中刪除指定元素的單個實(shí)例(如果存在)。Object poll()
:檢索并刪除此隊(duì)列的頭部,如果此隊(duì)列為空,則返回null。Object element()
:檢索但不刪除此隊(duì)列的頭部,如果此隊(duì)列為空,則返回null。Object peek()
:檢索但不刪除此隊(duì)列的頭部,如果此隊(duì)列為空,則返回null。void clear()
:從此優(yōu)先級隊(duì)列中刪除所有元素。Comparator comparator()
:返回用于對此隊(duì)列中的元素進(jìn)行排序的比較器,如果此隊(duì)列根據(jù)其元素的自然順序排序,則返回null。boolean contains(Object o)
:如果此隊(duì)列包含指定的元素,則返回true。int size()
:返回此隊(duì)列中的元素數(shù)。Object [] toArray()
:返回包含此隊(duì)列中所有元素的數(shù)組。
上圖中我們給每個元素按照層序遍歷的方式進(jìn)行了編號,如果你足夠細(xì)心,會發(fā)現(xiàn)父節(jié)點(diǎn)和子節(jié)點(diǎn)的編號是有聯(lián)系的,更確切的說父子節(jié)點(diǎn)的編號之間有如下關(guān)系:
leftNo = parentNo*2+1
rightNo = parentNo*2+2
parentNo = (nodeNo-1)/2
通過上述三個公式,可以輕易計算出某個節(jié)點(diǎn)的父節(jié)點(diǎn)以及子節(jié)點(diǎn)的下標(biāo)。這也就是為什么可以直接用數(shù)組來存儲堆的原因。
PriorityQueue的peek()和element操作是常數(shù)時間,add(), offer(), 無參數(shù)的remove()以及poll()方法的時間復(fù)雜度都是log(N)。
public boolean offer(E e) {if (e == null)//不允許放入null元素
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);//自動擴(kuò)容
size = i + 1;
if (i == 0)//隊(duì)列原來為空,這是插入的第一個元素
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) {Comparable super E>key = (Comparable super E>) 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ù)向上比較,否則停止比較的過程
前言: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級流量清洗系統(tǒng)配攻擊溯源,準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性,企業(yè)級服務(wù)器適合批量采購,新人活動首月15元起,快前往官網(wǎng)查看詳情吧
分享文章:PriorityQueue詳解-創(chuàng)新互聯(lián)
網(wǎng)站路徑:http://aaarwkj.com/article32/dgogpc.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供標(biāo)簽優(yōu)化、服務(wù)器托管、域名注冊、企業(yè)建站、電子商務(wù)、外貿(mào)網(wǎng)站建設(shè)
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請盡快告知,我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時需注明來源: 創(chuàng)新互聯(lián)
猜你還喜歡下面的內(nèi)容