一、優先級樹是什么

優先級樹的根節點中存儲的元素具有最小優先級。

優先級樹是滿足下面這些條件的二叉樹:

1、樹中的每一個節點存儲一個元素；

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

當一個優先級樹是一個近似滿二叉樹時，就是稱之為堆了，或者偏序樹。

區別于二叉排序樹（BST），優先級樹通常只有偏序，即根的優先級大于左右子樹，并且遞歸定義左右子樹各自也是一顆優先級樹。通常意義上講，就是數據結構里的堆，常見實現是通過數組表示的完全二叉堆。

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

延伸閱讀：

二、優先級隊列(PriorityQueue)

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

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

//Go語言表示

type PriorityQueue struct {

???? //隱藏實現

?}

??

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

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

??

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

針對不同實現，優先級隊列的插入和刪除方法的效率是不同的。