優(yōu)先級隊列是一種特殊類型的隊列，其中每個元素都與一個優(yōu)先級值相關(guān)聯(lián)。并且，元素根據(jù)其優(yōu)先級提供服務(wù)。即，首先服務(wù)更高優(yōu)先級的元素。

但是，如果出現(xiàn)具有相同優(yōu)先級的元素，則按照它們在隊列中的順序提供服務(wù)。

分配優(yōu)先級值

通常，在分配優(yōu)先級時考慮元素本身的值。例如，

具有最高值的元素被認(rèn)為是最高優(yōu)先級的元素。但是，在其他情況下，我們可以假設(shè)具有最低值的元素作為最高優(yōu)先級元素。

我們還可以根據(jù)需要設(shè)置優(yōu)先級。

優(yōu)先隊列和普通隊列的區(qū)別

在隊列中，執(zhí)行先進(jìn)先出規(guī)則，而在優(yōu)先級隊列中，根據(jù)優(yōu)先級刪除值。首先刪除具有最高優(yōu)先級的元素。

優(yōu)先隊列的實現(xiàn)

優(yōu)先隊列可以使用數(shù)組、鏈表、堆數(shù)據(jù)結(jié)構(gòu)或二叉搜索樹來實現(xiàn)。在這些數(shù)據(jù)結(jié)構(gòu)中，堆數(shù)據(jù)結(jié)構(gòu)提供了優(yōu)先隊列的有效實現(xiàn)。

因此，我們將在本教程中使用堆數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)優(yōu)先級隊列。在以下操作中實現(xiàn)了最大堆。

優(yōu)先隊列操作

優(yōu)先級隊列的基本操作是插入、移除和查看元素。

在研究優(yōu)先隊列之前，請參考堆數(shù)據(jù)結(jié)構(gòu)以更好地理解二叉堆，因為它用于實現(xiàn)本文中的優(yōu)先隊列。

1. 將元素插入優(yōu)先隊列

通過以下步驟將元素插入優(yōu)先級隊列(最大堆)。

在樹的末尾插入新元素。

堆肥樹。

將元素插入優(yōu)先級隊列的算法(最大堆)

如果沒有節(jié)點，則創(chuàng)建一個新節(jié)點。否則(一個節(jié)點已經(jīng)存在)在末尾插入新節(jié)點(從左到右的最后一個節(jié)點。)

堆化數(shù)組對于最小堆，上述算法被修改parentNode為始終小于newNode。

2. 從優(yōu)先隊列中刪除一個元素

從優(yōu)先級隊列(最大堆)中刪除元素的操作如下：

選擇要刪除的元素。

與最后一個元素交換它。

刪除最后一個元素。

堆肥樹。

刪除優(yōu)先隊列中元素的算法(最大堆)

如果nodeToBeDeleted是leafNode，則移除節(jié)點，否則交換nodeToBeDeleted與lastLeafNode，移除noteToBeDeleted

堆化數(shù)組對于最小堆，修改了上述算法，使兩者childNodes都小于currentNode。

3.從優(yōu)先隊列偷看(查找最大值/最小值)

Peek 操作返回最大堆的最大元素或最小堆的最小元素，而不刪除節(jié)點。

對于最大堆和最小堆

返回根節(jié)點

4.從優(yōu)先隊列中提取Max/Min

Extract-Max 返回從最大堆中刪除后具有最大值的節(jié)點，而 Extract-Min 返回從最小堆中刪除后具有最小值的節(jié)點。

如果大家想了解更相關(guān)知識，可以關(guān)注一下動力節(jié)點的Java在線學(xué)習(xí)，里面的內(nèi)容從入門到精通，對于初學(xué)者來說會有很大幫助。