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]

次に、1 から 100 までの乱数の束を含む 2 つのリストがあり、いくつかの繰り返しがありました。

    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 に答える