python - 确定数字列表是否按堆顺序，Python 3.2

Question

我刚刚发现了堆(在现实生活中和 Python 中)，现在我正在尝试确定某个随机数列表是否按堆顺序排列。
问题是我不确定自己在实践中是否真正理解“堆”，尽管我相信所提供的定义是有意义的。

我发现了一些练习题，应该可以帮助您编写堆伪代码。这就是问题所在，下面是我尝试解决它的方法:

编写一个函数来检查数字列表是否是堆:

给定一个列表，如果数字按堆顺序排列，则返回 True，如果数字不按堆顺序排列，则返回 False，并让程序返回并打印答案。

示例:

• 返回 True:以下列表按堆顺序排列: [0,1, 10, 2, 3, 11, 12, 4, 5, 19, 15]
• 返回 False以下列表不按堆顺序排列:[0, 1, 10, 2, 15, 11, 12, 4, 5, 19, 3]

然后有 2 个列表，其中包含一堆从 1 到 100 的随机数，并且有些是重复的。

    def heap_or(A):
      n = len(A)
      for i in range(n):
        start = (len(A) - 2) / 2
        while start >= 0:
          siftDown(A, start, len(A) - 1)
          start -= 1:
             return 'True'
        else:
             return 'False'

    def siftDown(A, start, end):
    root = start
    while root * 2 + 1 <= end:
        number = root * 2 + 1
        if number + 1 <= end and A[number] < A[number + 1]:
            number += 1
        if number <= end and A[root] < A[number]:
            A[root], A[number] = A[number], A[root]
            root = number
        else:
            return

     print 

有人可以帮我一下吗？因为我不太确定我是否正确定义了堆，所以代码也给我带来了困难!

Answer 1

堆属性(对于最大堆)是每个节点都应该大于或等于其父节点。存储在数组中的二叉堆中元素 i 的父元素是元素 (i - 1)//2:

def is_heap(A):
    return all(A[i] >= A[(i - 1) // 2] for i in range(1, len(A)))

显然，因为堆存储在数组中，所以我们不需要检查形状。