參考鏈接：https://github.com/itcharge/LeetCode-Py
一智润、簡介
優(yōu)先隊列（Priority Queue）：一種特殊的隊列赏迟。在優(yōu)先隊列中好芭，元素被賦予優(yōu)先級虑凛，當訪問隊列元素時邑蒋，具有最高優(yōu)先級的元素最先刪除栓票。
優(yōu)先隊列與普通隊列最大的不同點在于出隊順序司训。
- 普通隊列的出隊順序跟入隊順序相關(guān)耘子，符合「先進先出（First in, First out）」的規(guī)則。
- 而優(yōu)先隊列的出隊順序跟入隊順序無關(guān)她我，優(yōu)先隊列是按照元素的優(yōu)先級來決定出隊順序的虹曙。優(yōu)先級高的元素優(yōu)先出隊，優(yōu)先級低的元素后出隊番舆。優(yōu)先隊列符合 「最高級先出（First in, Largest out）」 的規(guī)則酝碳。
二、適用場景
- 數(shù)據(jù)壓縮：赫夫曼編碼算法恨狈；
- 最短路徑算法：Dijkstra 算法疏哗；
- 最小生成樹算法：Prim 算法；
- 任務(wù)調(diào)度器：根據(jù)優(yōu)先級執(zhí)行系統(tǒng)任務(wù)禾怠；
- 事件驅(qū)動仿真：顧客排隊算法返奉；
- 選擇問題：查找第 k 個最小元素。
- Python 中也可以通過 heapq 來實現(xiàn)優(yōu)先隊列吗氏。
三芽偏、實現(xiàn)方式
優(yōu)先隊列所涉及的基本操作跟普通隊列差不多，主要是 「入隊操作」 和 「出隊操作」弦讽。
而優(yōu)先隊列的實現(xiàn)方式也有很多種污尉，除了使用「數(shù)組（順序存儲）實現(xiàn)」與「鏈表（鏈式存儲）實現(xiàn)」之外，我們最常用的是使用 「二叉堆結(jié)構(gòu)實現(xiàn)」優(yōu)先隊列往产。
以下是三種方案的介紹和總結(jié)被碗。
- 數(shù)組（順序存儲）實現(xiàn)優(yōu)先隊列：入隊操作直接插入到數(shù)組隊尾，時間復(fù)雜度為
仿村。出隊操作需要遍歷整個數(shù)組蛮放，找到優(yōu)先級最高的元素，返回并刪除該元素奠宜，時間復(fù)雜度為
包颁。
- 鏈表（鏈式存儲）實現(xiàn)優(yōu)先隊列：鏈表中的元素按照優(yōu)先級排序瞻想，入隊操作需要為待插入元素創(chuàng)建節(jié)點，并在鏈表中找到合適的插入位置娩嚼，時間復(fù)雜度為
- 二叉堆結(jié)構(gòu)實現(xiàn)優(yōu)先隊列：構(gòu)建一個二叉堆結(jié)構(gòu)，二叉堆按照優(yōu)先級進行排序贵少。入隊操作就是將元素插入到二叉堆中合適位置呵俏，時間復(fù)雜度為
。吹對操作則返回二叉堆中優(yōu)先級最大節(jié)點并刪除滔灶，時間復(fù)雜度也是
三種結(jié)構(gòu)實現(xiàn)的優(yōu)先隊列入隊操作和出隊操作的時間復(fù)雜度總結(jié)如下：
時間復(fù)雜度對比圖
四、總結(jié)
經(jīng)過為期半個月的力扣刷題學(xué)習(xí)录平，我從害怕做題到有一點點興趣麻车，我覺得這件事情是值得繼續(xù)堅持下去的，雖然現(xiàn)在還是不太懂斗这，至少在旁邊轉(zhuǎn)悠动猬，繼續(xù)前進應(yīng)該能到門邊上的。這次課程的設(shè)計者非常用心表箭，知識點很細致赁咙，而且很全面，可能有一點點小的誤差被其他同學(xué)發(fā)現(xiàn)了免钻，但這是一件更好的事情彼水，不斷地改進將會得到更進一步的提升。
