點擊上方"java全棧技術"關注，每天學習一個java知識點
轉自：程序員小灰
隊列的特點是什麼？
聰明的小夥伴們都知道，是先進先出（FIFO）。
入隊列：
出隊列：
那麼，優先隊列又是什麼樣子呢？
優先隊列不再遵循先入先出的原則，而是分為兩種情況：
最大優先隊列，無論入隊順序，當前最大的元素優先出隊。
最小優先隊列，無論入隊順序，當前最小的元素優先出隊。
比如有一個最大優先隊列，它的最大元素是8，那麼雖然元素8並不是隊首元素，但出隊的時候仍然讓元素8首先出隊：
要滿足以上需求，利用線性數據結構並非不能實現，但是時間複雜度較高，最壞時間複雜度O（n），並不是最理想的方式。
至於為什麼最壞時間複雜度是O（n），大家可以思考下。
讓我們回顧一下二叉堆的特性：
1.最大堆的堆頂是整個堆中的最大元素
2.最小堆的堆頂是整個堆中的最小元素
因此，我們可以用最大堆來實現最大優先隊列，每一次入隊操作就是堆的插入操作，每一次出隊操作就是刪除堆頂節點。
入隊操作：
1.插入新節點5
2.新節點5上浮到合適位置。
出隊操作：
1.把原堆頂節點10“出隊”
2.最後一個節點1替換到堆頂位置
3.節點1下沉，節點9成為新堆頂
代碼中採用數組來存儲二叉堆的元素，因此當元素超過數組範圍的時候，需要進行resize來擴大數組長度。
分享到:
閱讀更多 java全棧技術 的文章
