java中的PriorityQueue類過程詳解
一、什麼是優先級隊列
1、概念
我們都知道隊列，隊列的核心思想就是先進先出，這個優先級隊列有點不太一樣。優先級隊列中，數據按關鍵詞有序排列，插入新數據的時候，會自動插入到合適的位置保證隊列有序。（順序有兩種形式：升序或者是降序）
來一個標準點的定義：
PriorityQueue類在Java1.5中引入。PriorityQueue是基於優先堆的一個無界隊列，這個優先隊列中的元素可以默認自然排序或者通過提供的Comparator（比較器）在隊列實例化的時排序。要求使用Java Comparable和Comparator接口給對象排序，並且在排序時會按照優先級處理其中的元素。
比如我們往隊列裡面插入132，插入2的時候，就會在內部調整為123（默認順序是升序）。正是由於這個優良特性可以幫助我們實現一系列問題。我們先看一個例子，體會一下他的優點，然後再看一下為什麼能夠實現這樣的功能。
我們看到就算是我們隨意插入數據，但是輸出的結果總是有序的，這樣一來優先級隊列就可以有瞭很多個使用場景。下面給出一道力扣題。體會一下他的優點。
2、案例演示特性
Leetcode215題：在未排序的數組中找到第 k個最大的元素。請註意，你需要找的是數組排序後的第 k 個最大的元素，而不是第 k 個不同的元素。
輸入：3,2,3,1,2,4,5,5,6，k = 4。輸出就是5，因此重復的並不考慮。我們一般情況下一般首先想到冒泡排序。每一次都冒出來一個最小的元素，這樣冒K次，就是我們想要的結果。
其實冒泡排序還可以解決另外一個問題，那就是返回倒數第K大的元素，方法是每次冒出來一個最大的元素即可。
這樣做很簡單，但是需要我們自己手寫冒泡排序，下面我們看使用優先級隊列如何解決的。
就這幾行代碼就搞定瞭，是不是超級簡單。為什麼優先級隊列能夠實現呢？下面我們來分析一下他的數據結構：
3、數據結構
優先級隊列底層的數據結構其實是一顆二叉堆，什麼是二叉堆呢？我們來看看
在這裡我們會發現以下特征：
（1）二叉堆是一個完全二叉樹
（2）根節點總是大於左右子節點（大頂堆），或者是小於左右子節點（小頂堆）。
如果我們要插入一個節點怎麼辦呢？
自己使用畫圖工具畫的，能看懂就行，不要在意那些細節兄弟。過程如下：
（1）找到待插入位置：滿足完全二叉樹的特點，依次插入
（2）插入之後判斷是否滿足二叉堆的性質，不滿足那就調整
（3）1<>6交換，發現不滿足，1<>4交換，滿足即停止。
對於我們的優先級隊列就是這樣的一種數據結構，因此我們在插入的時候保證瞭數據的有序性。
OK。到這基本上我們能夠體會到優先級隊列的思想瞭。來一個小結：
優先級隊列使用二叉堆的特點，可以使得插入的數據自動排序（升序或者是降序）。
到此這篇關於java中的PriorityQueue類的文章就介紹到這瞭,更多相關java PriorityQueue類內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！
推薦閱讀：
- Java中PriorityQueue實現最小堆和最大堆的用法
- 淺談Java中Collections.sort對List排序的兩種方法
- Java stream sorted使用 Comparator 進行多字段排序的方法
- 深入淺出講解Java比較器及數學常用類
- Java元素排序Comparable與Comparator的區別