一、什么是優(yōu)先級隊(duì)列

1、概念

我們都知道隊(duì)列，隊(duì)列的核心思想就是先進(jìn)先出，這個優(yōu)先級隊(duì)列有點(diǎn)不太一樣。優(yōu)先級隊(duì)列中，數(shù)據(jù)按關(guān)鍵詞有序排列，插入新數(shù)據(jù)的時(shí)候，會自動插入到合適的位置保證隊(duì)列有序。（順序有兩種形式：升序或者是降序）

來一個標(biāo)準(zhǔn)點(diǎn)的定義：

PriorityQueue類在Java1.5中引入。PriorityQueue是基于優(yōu)先堆的一個無界隊(duì)列，這個優(yōu)先隊(duì)列中的元素可以默認(rèn)自然排序或者通過提供的Comparator（比較器）在隊(duì)列實(shí)例化的時(shí)排序。要求使用Java Comparable和Comparator接口給對象排序，并且在排序時(shí)會按照優(yōu)先級處理其中的元素。

比如我們往隊(duì)列里面插入132，插入2的時(shí)候，就會在內(nèi)部調(diào)整為123（默認(rèn)順序是升序）。正是由于這個優(yōu)良特性可以幫助我們實(shí)現(xiàn)一系列問題。我們先看一個例子，體會一下他的優(yōu)點(diǎn)，然后再看一下為什么能夠?qū)崿F(xiàn)這樣的功能。

我們看到就算是我們隨意插入數(shù)據(jù)，但是輸出的結(jié)果總是有序的，這樣一來優(yōu)先級隊(duì)列就可以有了很多個使用場景。下面給出一道力扣題。體會一下他的優(yōu)點(diǎn)。

2、案例演示特性

Leetcode215題：在未排序的數(shù)組中找到第 k個最大的元素。請注意，你需要找的是數(shù)組排序后的第 k 個最大的元素，而不是第 k 個不同的元素。

輸入：3,2,3,1,2,4,5,5,6，k = 4。輸出就是5，因此重復(fù)的并不考慮。我們一般情況下一般首先想到冒泡排序。每一次都冒出來一個最小的元素，這樣冒K次，就是我們想要的結(jié)果。

其實(shí)冒泡排序還可以解決另外一個問題，那就是返回倒數(shù)第K大的元素，方法是每次冒出來一個最大的元素即可。

這樣做很簡單，但是需要我們自己手寫冒泡排序，下面我們看使用優(yōu)先級隊(duì)列如何解決的。

就這幾行代碼就搞定了，是不是超級簡單。為什么優(yōu)先級隊(duì)列能夠?qū)崿F(xiàn)呢？下面我們來分析一下他的數(shù)據(jù)結(jié)構(gòu)：

3、數(shù)據(jù)結(jié)構(gòu)

優(yōu)先級隊(duì)列底層的數(shù)據(jù)結(jié)構(gòu)其實(shí)是一顆二叉堆，什么是二叉堆呢？我們來看看

在這里我們會發(fā)現(xiàn)以下特征：

（1）二叉堆是一個完全二叉樹

（2）根節(jié)點(diǎn)總是大于左右子節(jié)點(diǎn)（大頂堆），或者是小于左右子節(jié)點(diǎn)（小頂堆）。

如果我們要插入一個節(jié)點(diǎn)怎么辦呢？

自己使用畫圖工具畫的，能看懂就行，不要在意那些細(xì)節(jié)兄弟。過程如下：

（1）找到待插入位置：滿足完全二叉樹的特點(diǎn)，依次插入

（2）插入之后判斷是否滿足二叉堆的性質(zhì)，不滿足那就調(diào)整

（3）1<>6交換，發(fā)現(xiàn)不滿足，1<>4交換，滿足即停止。

對于我們的優(yōu)先級隊(duì)列就是這樣的一種數(shù)據(jù)結(jié)構(gòu)，因此我們在插入的時(shí)候保證了數(shù)據(jù)的有序性。

OK。到這基本上我們能夠體會到優(yōu)先級隊(duì)列的思想了。來一個小結(jié)：

優(yōu)先級隊(duì)列使用二叉堆的特點(diǎn)，可以使得插入的數(shù)據(jù)自動排序（升序或者是降序）。

到此這篇關(guān)于java中的PriorityQueue類的文章就介紹到這了,更多相關(guān)java PriorityQueue類內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論