初始化區間堆

區間堆與嵌入式最小-最大堆相同，其中每個節點包含兩個元素。它被定義為一個完全二叉樹，其中

  • 左元素小於或等於右元素。
  • 這兩個元素都定義了一個閉區間。
  • 除根節點外的任何節點所表示的區間都是父節點的子區間。
  • 左側的元素表示最小堆。
  • 右側的元素表示最大堆。

根據元素的數量，允許兩種情況：

  • 偶數個元素：在這種情況下，每個節點包含兩個元素，例如 a 和 b，其中 a ≤ b。然後每個節點都由區間 [a, b] 表示。
  • 奇數個元素：在這種情況下，除最後一個節點外的每個節點都包含兩個元素，由區間 [a, b] 表示，而最後一個節點將包含單個元素，並由區間 [a, b] 表示。

可以使用與初始化普通堆相同的策略來初始化區間堆——從堆底到根依次處理，確保每個子樹都被表示為區間堆。對於每個子樹，首先對根節點中的元素進行排序；然後再次插入此子樹根節點的左端點，實現用於 removeMin 函式的重新插入策略，然後再次插入此子樹根節點的右端點，實現用於 removeMax 函式的策略。

更新於： 2020年1月3日

243 次瀏覽

開啟您的 職業生涯

透過完成課程獲得認證

立即開始
廣告