一、優先級樹是什么
優先級樹的根節點中存儲的元素具有最小優先級。
優先級樹是滿足下面這些條件的二叉樹:
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 //從優先級隊列中取出優先級較高的元素
針對不同實現,優先級隊列的插入和刪除方法的效率是不同的。