快捷導(dǎo)航

Java優(yōu)先隊(duì)列?priority?queue

更新時(shí)間：2022年01月25日 11:48:47 作者：L-M-Y

本文主要介紹了Java優(yōu)先隊(duì)列?priority?queue，優(yōu)先隊(duì)列是一種特殊的數(shù)據(jù)結(jié)構(gòu)隊(duì)列中每一個(gè)元素都被分配到一個(gè)優(yōu)先權(quán)值,出隊(duì)順序按照優(yōu)先權(quán)值來(lái)劃分。一般有兩種出隊(duì)順序高優(yōu)先權(quán)出隊(duì)或低優(yōu)先權(quán)出隊(duì),想了解具體內(nèi)容的小伙伴可以參考下文內(nèi)容,希望對(duì)你有所幫助

1.優(yōu)先隊(duì)列概念

優(yōu)先隊(duì)列（priority queue）是一種特殊的數(shù)據(jù)結(jié)構(gòu)。
隊(duì)列中每一個(gè)元素都被分配到一個(gè)優(yōu)先權(quán)值，出隊(duì)順序按照優(yōu)先權(quán)值來(lái)劃分。
一般有兩種出隊(duì)順序：高優(yōu)先權(quán)出隊(duì)或低優(yōu)先權(quán)出隊(duì)。
priority queue至少要有兩個(gè)最基本的ADT：進(jìn)隊(duì)，出隊(duì)（按照高優(yōu)先權(quán)或低優(yōu)先權(quán)）

產(chǎn)生原因：同樣是為了提高數(shù)據(jù)處理的效率。試想，要實(shí)現(xiàn)優(yōu)先隊(duì)列對(duì)應(yīng)的功能，若使用鏈表或者數(shù)組，那么要么先排序再插入，要么先插入再查找最大最小元素。這樣一來(lái)，入隊(duì)出隊(duì)的時(shí)間復(fù)雜度至少為O(N)。

優(yōu)先隊(duì)列出隊(duì)和入隊(duì)的時(shí)間復(fù)雜度均為O(log N)。
優(yōu)先隊(duì)列基于二叉堆實(shí)現(xiàn)。

2.二叉堆（Heap）

堆是一種特殊的二叉樹(shù)，性質(zhì)如下：

每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值（大頂堆），或每個(gè)結(jié)點(diǎn)的值都小宇或等于其左右孩子的值（小頂堆）。
必須滿(mǎn)足完全二叉樹(shù)的結(jié)構(gòu)。

完全二叉樹(shù)和滿(mǎn)二叉樹(shù)

完全二叉樹(shù) complete binary tree

葉節(jié)點(diǎn)只可能出現(xiàn)在最后兩層，且最后一層的葉節(jié)點(diǎn)都左對(duì)齊
一棵深度為h的完全二叉樹(shù)

滿(mǎn)二叉樹(shù) full binary tree

深度為h的滿(mǎn)二叉樹(shù)有（2^h）-1個(gè)結(jié)點(diǎn)

由二叉堆的定義可以看出，跟結(jié)點(diǎn)一定是二叉堆中結(jié)點(diǎn)值最大（或最?。┑?。較大（或較小）的結(jié)點(diǎn)靠近根節(jié)點(diǎn)

堆的存儲(chǔ)結(jié)構(gòu)：

一般情況下，堆用數(shù)組來(lái)存儲(chǔ)，第i個(gè)結(jié)點(diǎn)的父節(jié)點(diǎn)的下標(biāo)就是（i-1）/2.
如果用層序遍歷順序?qū)⒋箜敹押托№敹汛嫒霐?shù)組，

則關(guān)系如圖：

堆的重要操作

插入：插入一個(gè)元素之后，新元素首先被插入表層（即最后一層盡可能左邊的位置），之后再根據(jù)堆的性質(zhì)進(jìn)行調(diào)整。

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

刪除：刪除總是發(fā)生在根處，之后將最后一個(gè)元素（即最后一層最右邊的元素）拿來(lái)填補(bǔ)空缺，之后根據(jù)堆的性質(zhì)進(jìn)行調(diào)整堆的結(jié)構(gòu)。

到此這篇關(guān)于Java優(yōu)先隊(duì)列 priority queue的文章就介紹到這了,更多相關(guān)優(yōu)先隊(duì)列 priority queue內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: