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

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

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

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

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

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

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

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

延伸閱讀：

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

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

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

//Go語(yǔ)言表示

type PriorityQueue struct {

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

?}

??

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

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

??

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

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