最小-最大堆

最小-最大堆被定義為包含交替的最小（偶數）和最大（奇數）層次的完全二叉樹。偶數層次表示為例如 0、2、4 等，奇數層次表示為 1、3、5 等。

我們將在下一部分中認為根元素位於第一層，即 0。

最小-最大堆示例

最小-最大堆的特徵

  • 最小-最大堆中的每個節點都與資料成員（通常稱為鍵）相關聯，其值用於計算節點在最小-最大堆中的順序。
  • 根元素是最小-最大堆中的最小元素。
  • 作為最大（奇數）層次的第二層中的兩個元素之一的最大元素是最小-最大堆中的最大元素
  • 假設 y 是最小-最大堆中的任意節點。
  • 如果 y 位於最小（偶數）層次，則 y.key 是具有根節點 y 的子樹中所有鍵中最小的鍵。
  • 如果 y 位於最大（奇數）層次，則 y.key 是具有根節點 y 的子樹中所有鍵中最大的鍵。
  • 最小（最大）層次上的節點表示為最小（最大）節點。

最大-最小堆定義為最小-最大堆的反義詞；在這樣的堆中，最高值儲存在根節點中，而最小值儲存在根節點的一個子節點中。

更新於：2020 年 01 月 03 日

6 千多次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始
廣告