? ? 普通隊(duì)列(queue)是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，元素在隊(duì)列尾追加，而從隊(duì)列頭刪除。在優(yōu)先隊(duì)列中，元素被賦予優(yōu)先級(jí)。當(dāng)訪問(wèn)元素時(shí)，具有最高優(yōu)先級(jí)的元素最先刪除。

????優(yōu)先隊(duì)列（priority queue）具有最高級(jí)先出的行為特征。優(yōu)先隊(duì)列是0個(gè)或多個(gè)元素的集合，每個(gè)元素都有一個(gè)優(yōu)先權(quán)或值，對(duì)優(yōu)先隊(duì)列執(zhí)行的操作有1）查找；2）插入一個(gè)新元素；3)刪除。在最小優(yōu)先隊(duì)列，查找操作用來(lái)搜索優(yōu)先權(quán)最小的元素，刪除操作用來(lái)刪除該元素；對(duì)于最大優(yōu)先隊(duì)列，查找操作用來(lái)搜索優(yōu)先權(quán)最大的元素，刪除操作用來(lái)刪除該元素。優(yōu)先權(quán)隊(duì)列中的元素可以有相同的優(yōu)先權(quán)，查找與刪除操作可根據(jù)任意優(yōu)先權(quán)進(jìn)行。

????在算法設(shè)計(jì)中，經(jīng)常用到從序列中找一個(gè)最小值（或最大值）的操作，例如最短路徑、哈夫曼編碼等都需要找最小值。如果序列中順序查找最小值（或最大值）需要O(n)的時(shí)間，而使用優(yōu)先隊(duì)列找最小值（或最大值）則只需要O(logn)的時(shí)間。

????優(yōu)先隊(duì)列是利用堆來(lái)實(shí)現(xiàn)的，堆可以看作一顆完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)，在這棵完全二叉樹(shù)中，如果每一個(gè)結(jié)點(diǎn)的值都大于等于左右孩子的值，則稱為最大堆。如果每一個(gè)結(jié)點(diǎn)的值都小于等于左右孩子的值，稱為最小堆。

????根據(jù)完全二叉樹(shù)的性質(zhì)，如果一個(gè)結(jié)點(diǎn)的下標(biāo)為 i ,則其左孩子的下標(biāo)為 2i, 其右孩子下標(biāo)為2i+1，其雙親的下標(biāo)為 i/2。且具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為[log2n] +1。

????普通的隊(duì)列是先進(jìn)先出的，而優(yōu)先隊(duì)列與普通隊(duì)列不同，每次出隊(duì)時(shí)按照優(yōu)先級(jí)順序出隊(duì)。例如，最小值（或最大值）出隊(duì)，優(yōu)先隊(duì)列中的記錄存儲(chǔ)滿足堆的定義。優(yōu)先隊(duì)列除了構(gòu)建初始堆之外，有出隊(duì)和入隊(duì)兩種常用的操作。

算法步驟：

1）構(gòu)建初始堆。

2）出隊(duì)：堆頂出隊(duì)，最后一個(gè)記錄代替堆頂?shù)奈恢?，重新調(diào)整為堆。

3）入隊(duì)：新記錄放入最后一個(gè)記錄之后，重新調(diào)整為堆。?

出隊(duì)：調(diào)整堆的過(guò)程就是堆頂從根“下沉”到葉子的過(guò)程。

入隊(duì)：入隊(duì)后除了新入隊(duì)記錄之外，其他結(jié)點(diǎn)都滿足最大堆的定義，只需要將新記錄執(zhí)行“上浮”操作，即可調(diào)整為堆。

代碼實(shí)現(xiàn)：

算法分析：

優(yōu)先隊(duì)列是利用堆實(shí)現(xiàn)的一種特殊隊(duì)列，堆是按照完全二叉樹(shù)的邏輯來(lái)順序存儲(chǔ)的，具有 n 個(gè)結(jié)點(diǎn)的完全的二叉樹(shù)的深度為 [log2n] +1。出隊(duì)時(shí)，堆頂元素出隊(duì)，最后一個(gè)元素代替堆頂，新的堆頂從根下沉到葉子，最多達(dá)到樹(shù)的深度，時(shí)間復(fù)雜度為O(log n);入隊(duì)時(shí)，新元素從葉子上浮到根，最多達(dá)到樹(shù)的深度，時(shí)間復(fù)雜度也為 O(logn)。優(yōu)先隊(duì)列的入隊(duì)和出隊(duì)操作間復(fù)雜度均為 O(logn)，因此在n 個(gè)元素的優(yōu)先隊(duì)列中找一個(gè)最小值（或最大值）的時(shí)間復(fù)雜度為O(log n)。想找到一個(gè)最大值就是最大堆，找最小值就用最小堆。