在 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

Arnab Chakraborty

更新时间：2021 年 10 月 14 日

1K+ 次浏览

开启您 职业生涯

完成课程获得认证

开始学习