国产一区二区精品-国产一区二区精品久-国产一区二区精品久久-国产一区二区精品久久91-免费毛片播放-免费毛片基地

千鋒教育-做有情懷、有良心、有品質的職業教育機構

手機站
千鋒教育

千鋒學習站 | 隨時隨地免費學

千鋒教育

掃一掃進入千鋒手機站

領取全套視頻
千鋒教育

關注千鋒學習站小程序
隨時隨地免費學習課程

當前位置:首頁  >  技術干貨  > 優先級樹是什么?

優先級樹是什么?

來源:千鋒教育
發布人:xqq
時間: 2023-10-11 07:09:22 1696979362

一、優先級樹是什么

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

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

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 //從優先級隊列中取出優先級較高的元素

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

聲明:本站稿件版權均屬千鋒教育所有,未經許可不得擅自轉載。
10年以上業內強師集結,手把手帶你蛻變精英
請您保持通訊暢通,專屬學習老師24小時內將與您1V1溝通
免費領取
今日已有369人領取成功
劉同學 138****2860 剛剛成功領取
王同學 131****2015 剛剛成功領取
張同學 133****4652 剛剛成功領取
李同學 135****8607 剛剛成功領取
楊同學 132****5667 剛剛成功領取
岳同學 134****6652 剛剛成功領取
梁同學 157****2950 剛剛成功領取
劉同學 189****1015 剛剛成功領取
張同學 155****4678 剛剛成功領取
鄒同學 139****2907 剛剛成功領取
董同學 138****2867 剛剛成功領取
周同學 136****3602 剛剛成功領取
相關推薦HOT