java中的PriorityQueue類過程詳解
一、什么是優(yōu)先級隊列
1、概念
我們都知道隊列,隊列的核心思想就是先進(jìn)先出,這個優(yōu)先級隊列有點不太一樣。優(yōu)先級隊列中,數(shù)據(jù)按關(guān)鍵詞有序排列,插入新數(shù)據(jù)的時候,會自動插入到合適的位置保證隊列有序。(順序有兩種形式:升序或者是降序)
來一個標(biāo)準(zhǔn)點的定義:
PriorityQueue類在Java1.5中引入。PriorityQueue是基于優(yōu)先堆的一個無界隊列,這個優(yōu)先隊列中的元素可以默認(rèn)自然排序或者通過提供的Comparator(比較器)在隊列實例化的時排序。要求使用Java Comparable和Comparator接口給對象排序,并且在排序時會按照優(yōu)先級處理其中的元素。
比如我們往隊列里面插入132,插入2的時候,就會在內(nèi)部調(diào)整為123(默認(rèn)順序是升序)。正是由于這個優(yōu)良特性可以幫助我們實現(xiàn)一系列問題。我們先看一個例子,體會一下他的優(yōu)點,然后再看一下為什么能夠?qū)崿F(xiàn)這樣的功能。
我們看到就算是我們隨意插入數(shù)據(jù),但是輸出的結(jié)果總是有序的,這樣一來優(yōu)先級隊列就可以有了很多個使用場景。下面給出一道力扣題。體會一下他的優(yōu)點。
2、案例演示特性
Leetcode215題:在未排序的數(shù)組中找到第 k個最大的元素。請注意,你需要找的是數(shù)組排序后的第 k 個最大的元素,而不是第 k 個不同的元素。
輸入:3,2,3,1,2,4,5,5,6,k = 4。輸出就是5,因此重復(fù)的并不考慮。我們一般情況下一般首先想到冒泡排序。每一次都冒出來一個最小的元素,這樣冒K次,就是我們想要的結(jié)果。
其實冒泡排序還可以解決另外一個問題,那就是返回倒數(shù)第K大的元素,方法是每次冒出來一個最大的元素即可。
這樣做很簡單,但是需要我們自己手寫冒泡排序,下面我們看使用優(yōu)先級隊列如何解決的。
就這幾行代碼就搞定了,是不是超級簡單。為什么優(yōu)先級隊列能夠?qū)崿F(xiàn)呢?下面我們來分析一下他的數(shù)據(jù)結(jié)構(gòu):
3、數(shù)據(jù)結(jié)構(gòu)
優(yōu)先級隊列底層的數(shù)據(jù)結(jié)構(gòu)其實是一顆二叉堆,什么是二叉堆呢?我們來看看
在這里我們會發(fā)現(xiàn)以下特征:
(1)二叉堆是一個完全二叉樹
(2)根節(jié)點總是大于左右子節(jié)點(大頂堆),或者是小于左右子節(jié)點(小頂堆)。
如果我們要插入一個節(jié)點怎么辦呢?
自己使用畫圖工具畫的,能看懂就行,不要在意那些細(xì)節(jié)兄弟。過程如下:
(1)找到待插入位置:滿足完全二叉樹的特點,依次插入
(2)插入之后判斷是否滿足二叉堆的性質(zhì),不滿足那就調(diào)整
(3)1<>6交換,發(fā)現(xiàn)不滿足,1<>4交換,滿足即停止。
對于我們的優(yōu)先級隊列就是這樣的一種數(shù)據(jù)結(jié)構(gòu),因此我們在插入的時候保證了數(shù)據(jù)的有序性。
OK。到這基本上我們能夠體會到優(yōu)先級隊列的思想了。來一個小結(jié):
優(yōu)先級隊列使用二叉堆的特點,可以使得插入的數(shù)據(jù)自動排序(升序或者是降序)。
到此這篇關(guān)于java中的PriorityQueue類的文章就介紹到這了,更多相關(guān)java PriorityQueue類內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Java 實戰(zhàn)項目之小說在線閱讀系統(tǒng)的實現(xiàn)流程
讀萬卷書不如行萬里路,只學(xué)書上的理論是遠(yuǎn)遠(yuǎn)不夠的,只有在實戰(zhàn)中才能獲得能力的提升,本篇文章手把手帶你用java+SSM+jsp+mysql+maven實現(xiàn)前臺閱讀后臺管理的小說在線閱讀系統(tǒng),大家可以在過程中查缺補(bǔ)漏,提升水平2021-11-11Java 實戰(zhàn)練習(xí)之網(wǎng)上電商項目的實現(xiàn)
讀萬卷書不如行萬里路,只學(xué)書上的理論是遠(yuǎn)遠(yuǎn)不夠的,只有在實戰(zhàn)中才能獲得能力的提升,本篇文章手把手帶你用java+vue+Springboot+ssm+mysql+maven+redis實現(xiàn)一個網(wǎng)上電商項目,大家可以在過程中查缺補(bǔ)漏,提升水平2021-11-11深入探究Java?@MapperScan實現(xiàn)原理
之前是直接在Mapper類上面添加注解@Mapper,這種方式要求每一個mapper類都需要添加此注解,麻煩。通過使用@MapperScan可以指定要掃描的Mapper類的包的路徑,這篇文章深入探究Java?@MapperScan的實現(xiàn)原理2023-01-01