在 Python 中檢查堆是否形成最大堆的程式

假設我們有一個表示堆樹的列表。眾所周知，堆是一個完備二叉樹。我們必須檢查這些元素是否形成最大堆。眾所周知，對於最大堆，每個元素都大於其兩個子元素。

因此，如果輸入類似於 nums = [8, 6, 4, 2, 0, 3]，那麼輸出將為 True，因為所有元素都大於它們的子元素。

要解決此問題，我們將按照以下步驟進行 −

  • n := nums 的大小
  • 對於範圍為 0 到 n - 1 的 i，執行
    • m := i * 2
    • num := nums[i]
    • 如果 m + 1 < n，則
      • 如果 num < nums[m + 1]，則
        • 返回 False
    • 如果 m + 2 < n，則
      • 如果 num < nums[m + 2]，則
        • 返回 False
  • 返回 True

示例

讓我們看看以下實現以獲得更好的理解 −

def solve(nums):
   n = len(nums)
   for i in range(n):
      m = i * 2
      num = nums[i]
      if m + 1 < n:
         if num < nums[m + 1]:
            return False
      if m + 2 < n:
         if num < nums[m + 2]:
            return False
   return True

nums = [8, 6, 4, 2, 0, 3]
print(solve(nums))

輸入

[8, 6, 4, 2, 0, 3]

輸出

True

更新時間：2021 年 10 月 14 日

1K+ 次瀏覽

開啟您 職業生涯

完成課程獲得認證

開始學習
廣告