Java優先隊列 priority queue

1.優先隊列概念

優先隊列（priority queue）是一種特殊的數據結構。
隊列中每一個元素都被分配到一個優先權值，出隊順序按照優先權值來劃分。
一般有兩種出隊順序：高優先權出隊或低優先權出隊。
priority queue至少要有兩個最基本的ADT：進隊，出隊（按照高優先權或低優先權）

產生原因：同樣是為瞭提高數據處理的效率。試想，要實現優先隊列對應的功能，若使用鏈表或者數組，那麼要麼先排序再插入，要麼先插入再查找最大最小元素。這樣一來，入隊出隊的時間復雜度至少為O(N)。

• 優先隊列出隊和入隊的時間復雜度均為O(log N)。
• 優先隊列基於二叉堆實現。

2.二叉堆（Heap）

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

• 每個結點的值都大於或等於其左右孩子結點的值（大頂堆），或每個結點的值都小宇或等於其左右孩子的值（小頂堆）。
• 必須滿足完全二叉樹的結構。

完全二叉樹和滿二叉樹

完全二叉樹 complete binary tree


葉節點隻可能出現在最後兩層，且最後一層的葉節點都左對齊
一棵深度為h的完全二叉樹

滿二叉樹 full binary tree


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

由二叉堆的定義可以看出，跟結點一定是二叉堆中結點值最大（或最小）的。較大（或較小）的結點靠近根節點

堆的存儲結構：

一般情況下，堆用數組來存儲，第i個結點的父節點的下標就是（i-1）/2.
如果用層序遍歷順序將大頂堆和小頂堆存入數組，

則關系如圖：

堆的重要操作

插入：插入一個元素之後，新元素首先被插入表層（即最後一層盡可能左邊的位置），之後再根據堆的性質進行調整。

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

刪除：刪除總是發生在根處，之後將最後一個元素（即最後一層最右邊的元素）拿來填補空缺，之後根據堆的性質進行調整堆的結構。

到此這篇關於Java優先隊列 priority queue的文章就介紹到這瞭,更多相關優先隊列 priority queue內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：

• Javascript數據結構之棧和隊列詳解
• C++中priority_queue模擬實現的代碼示例
• Java數據結構之最小堆和最大堆的原理及實現詳解
• C++實現LeetCode(102.二叉樹層序遍歷)
• Python數據結構之優先級隊列queue用法詳解