3

インターネットのどこかでこの質問を見て、解決しようとしました。ヒープが厳密にバイナリ ツリーである場合は解決できましたが (プリオーダー トラバーサルを繰り返し分割することにより)、ヒープが完全なバイナリ ツリーにすぎない場合のアルゴリズムを理解できませんでした。

たとえば1, 2, 3, 4, 5, 6, 7、最小ヒープの事前順トラバーサルの場合、

ヒープのサイズは7

1ヒープ内の最初の要素です (ヒープが配列として表されていることを考慮して)

次の(size - 1) / 2要素は、の左側のサブツリーにあります1

2, 3, 4の左側のサブツリーになります1

最後の(size - 1) / 2要素は、の右サブツリーにあります1

5, 6, 7の右側のサブツリーになります1

このロジックを再帰的に適用することで、完全なヒープを構築できます。

このソリューションは、ヒープが厳密にバイナリ ツリーであるような場合に機能します。

       1
    2     3
  4   5  6  7

しかし明らかに、これは非リーフ要素が 1 つまたはまったく子を持たないヒープの場合には機能しません。たとえば、

          1                1
       2     3         2     3
     4   5  6        4     5

同じことができるクリーンなアルゴリズムは思いつきませんでした。解決策/提案は本当に役に立ちます。

4

4 に答える 4

2

いくつかの例を見ると、これが簡単になります。子の数が増えると、次のパターンが見られます。

  • 子の数が2の場合、分割は次のようになります：（1、1）
  • 子の数が3の場合、分割は次のようになります：（2、1）

子の数が2から6の間のときにこの方法を続けると、次の分割が得られます。

(1, 1), (2, 1), (3, 1), (3, 2), (3, 3)

子供の数が6〜14の場合、次のようになります。

(3, 3), (4, 3), (5, 3), (6, 3), (7, 3), (7,4), (7, 5), (7, 6), (7, 7)

したがって、子の数が（2 ^ k-2）と（2 ^ {k + 1} -2）の間にある場合、次のようになります。

 either a split of the form (2^{k-1}-1+l, 2^{k-1}-1) where   0 <= l <= 2^{k-1} or
                            (2^k-1, 2^{k-1}-1+l)     where   0 <= l <= 2^{k-1}

その場合、ロジックは、（2 ^ k-2）<= childCount <=（2 ^ {k + 1} -2）となるようなakを見つけ、次のように分割することです。

Let l = childCount - (2^k-2)
If  l <= 2^{k-1} 
    split with (2^{k-1}-1+l, remaining)
Else 
    split with (2^k-1, remaining)
于 2012-09-21T13:46:43.833 に答える
0

preorder traversal では、ソートされた順序で要素を生成するヒープは、ベクトル (1,2,5,3,4,6,7) で表されます。inorder traversal がソートされた順序でキーを生成するヒープは存在しません。これは、ヒープでは、親が常にすべての子よりも小さいか、すべての子よりも大きいためです。(7,3,6,1,2,4,5) で表されるヒープは、ポストオーダー トラバーサル中にソートされた順序でキーを生成するヒープの例です。

于 2015-04-05T16:57:19.123 に答える
0

事前注文トラバーサルを標準のヒープ表現に変換するのは簡単です。予約注文は自分、左、右にアクセスします。1 から始まる配列のヒープの場合、ノード N の左側の子は 2N にあり、右側の子は 2N+1 です。これは、次のアルゴリズムに直接つながります。

def constructHeap(preorder, pidx, heap, hidx)  
    return pidx if (hidx>=heap.size)         #no more children
    heap[hidx] = preorder[pidx]              #self
    pidx = constructHeap(preorder, pidx+1, heap, hidx*2) #left
    return constructHeap(preorder, pidx, heap, hidx*2+1) #right
end

preorder = [1,2,3,4,5,6,7]
heap = Array.new(preorder.size+1)            #create storage
constructHeap(preorder, 0, heap, 1)
puts heap
于 2012-09-21T15:22:05.210 に答える
0

与えられた 2 つの情報のうちの 1 つだけを適用することで、これを解決しようとしています。

あなたが持っている情報は次のとおりです。

  • あなたは二分木を持っています
  • 上記のツリーはヒープソートされています

さて、3 番目のトラバーサルを取得するには通常 2 つのバイナリ トラバーサルが必要ですが (プレ、ポスト、インオーダーの 3 つです)、ここで追加情報があります:バイナリ ツリーはヒープです。

バイナリ ヒープは、常に完全なバイナリ ツリーです。完全な二分木は、常に左から右に埋められる最後のレベルを除いて、木のすべてのレベルが埋め尽くされている二分木のようなものです。つまり、ヒープが 2 つ未満の子を持つ内部ノードを持つことは不可能です。

于 2012-09-21T13:26:58.600 に答える