1.優(yōu)先隊列概念

優(yōu)先隊列（priority queue）是一種特殊的數(shù)據(jù)結(jié)構(gòu)。
隊列中每一個元素都被分配到一個優(yōu)先權(quán)值，出隊順序按照優(yōu)先權(quán)值來劃分。
一般有兩種出隊順序：高優(yōu)先權(quán)出隊或低優(yōu)先權(quán)出隊。
priority queue至少要有兩個最基本的ADT：進隊，出隊（按照高優(yōu)先權(quán)或低優(yōu)先權(quán)）

產(chǎn)生原因：同樣是為了提高數(shù)據(jù)處理的效率。試想，要實現(xiàn)優(yōu)先隊列對應(yīng)的功能，若使用鏈表或者數(shù)組，那么要么先排序再插入，要么先插入再查找最大最小元素。這樣一來，入隊出隊的時間復(fù)雜度至少為O(N)。

• 優(yōu)先隊列出隊和入隊的時間復(fù)雜度均為O(log N)。
• 優(yōu)先隊列基于二叉堆實現(xiàn)。

2.二叉堆（Heap）

堆是一種特殊的二叉樹，性質(zhì)如下：

• 每個結(jié)點的值都大于或等于其左右孩子結(jié)點的值（大頂堆），或每個結(jié)點的值都小宇或等于其左右孩子的值（小頂堆）。
• 必須滿足完全二叉樹的結(jié)構(gòu)。

完全二叉樹和滿二叉樹

完全二叉樹 complete binary tree

葉節(jié)點只可能出現(xiàn)在最后兩層，且最后一層的葉節(jié)點都左對齊
一棵深度為h的完全二叉樹

滿二叉樹 full binary tree

深度為h的滿二叉樹有（2^h）-1個結(jié)點

由二叉堆的定義可以看出，跟結(jié)點一定是二叉堆中結(jié)點值最大（或最小）的。較大（或較?。┑慕Y(jié)點靠近根節(jié)點

堆的存儲結(jié)構(gòu)：

一般情況下，堆用數(shù)組來存儲，第i個結(jié)點的父節(jié)點的下標就是（i-1）/2.
如果用層序遍歷順序?qū)⒋箜敹押托№敹汛嫒霐?shù)組，

則關(guān)系如圖：

堆的重要操作

插入：插入一個元素之后，新元素首先被插入表層（即最后一層盡可能左邊的位置），之后再根據(jù)堆的性質(zhì)進行調(diào)整。

例：寫出一次一個地將10,12,1,14,6,5,8,15,3,9,7,4,11,13和2插入一個初始為空的二叉堆的結(jié)果

刪除：刪除總是發(fā)生在根處，之后將最后一個元素（即最后一層最右邊的元素）拿來填補空缺，之后根據(jù)堆的性質(zhì)進行調(diào)整堆的結(jié)構(gòu)。

到此這篇關(guān)于Java優(yōu)先隊列 priority queue的文章就介紹到這了,更多相關(guān)優(yōu)先隊列 priority queue內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論