1

我刚刚发现了堆（在现实生活中和 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

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

4

1 回答 1

2

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

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

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

于 2013-05-07T11:12:15.267 回答