一、優(yōu)先級樹是什么

優(yōu)先級樹的根節(jié)點(diǎn)中存儲的元素具有最小優(yōu)先級。

優(yōu)先級樹是滿足下面這些條件的二叉樹:

1、樹中的每一個節(jié)點(diǎn)存儲一個元素；

2、任一節(jié)點(diǎn)中存儲的元素的優(yōu)先級不大于其兒子節(jié)點(diǎn)中元素的優(yōu)先級，從根到葉子節(jié)點(diǎn)的任一路徑上，各個節(jié)點(diǎn)中的元素按照優(yōu)先級的非減序排列。所以根節(jié)點(diǎn)中存儲的元素具有最小的優(yōu)先級。

當(dāng)一個優(yōu)先級樹是一個近似滿二叉樹時，就是稱之為堆了，或者偏序樹。

區(qū)別于二叉排序樹（BST），優(yōu)先級樹通常只有偏序，即根的優(yōu)先級大于左右子樹，并且遞歸定義左右子樹各自也是一顆優(yōu)先級樹。通常意義上講，就是數(shù)據(jù)結(jié)構(gòu)里的堆，常見實(shí)現(xiàn)是通過數(shù)組表示的完全二叉堆。

特性就是O(1)的堆頂查詢，O(logn)的刪除和插入。并且實(shí)現(xiàn)起來相對簡單，且不存在BST的退化情況。

延伸閱讀：

二、優(yōu)先級隊(duì)列(PriorityQueue)

優(yōu)先級隊(duì)列雖然也叫隊(duì)列，但是和普通的隊(duì)列還是有差別的。普通隊(duì)列出隊(duì)順序只取決于入隊(duì)順序，而優(yōu)先級隊(duì)列的出隊(duì)順序總是按照元素自身的優(yōu)先級。換句話說，優(yōu)先級隊(duì)列是一個自動排序的隊(duì)列。元素自身的優(yōu)先級可以根據(jù)入隊(duì)時間，也可以根據(jù)其他因素來確定，因此非常靈活。

優(yōu)先級隊(duì)列的內(nèi)部實(shí)現(xiàn)有很多種，例如有序數(shù)組、無序數(shù)組和堆等。但是無論哪種實(shí)現(xiàn)，優(yōu)先級隊(duì)列必須實(shí)現(xiàn)以下兩種方法：insert和delete。insert方法是將帶優(yōu)先級的元素插入優(yōu)先級隊(duì)列中（類似隊(duì)列的enQueue方法）；delete方法是從優(yōu)先級隊(duì)列中取出較高優(yōu)先級（或最低優(yōu)先級）的元素并在隊(duì)列中刪除該元素（類似隊(duì)列的出隊(duì)）。

//Go語言表示

type PriorityQueue struct {

???? //隱藏實(shí)現(xiàn)

?}

??

?//以int為例，值的大小即代表元素優(yōu)先級的高低（下同）

?func (pq *PriorityQueue)Insert(val int)? //插入帶優(yōu)先級的元素

??

?func (pq *PriorityQueue)Delete() int //從優(yōu)先級隊(duì)列中取出優(yōu)先級較高的元素

針對不同實(shí)現(xiàn)，優(yōu)先級隊(duì)列的插入和刪除方法的效率是不同的。