1

CLRS で指定された Build-Heap アルゴリズム

BUILD-MAX-HEAP(A)
1  heap-size[A] ← length[A]
2  for i ← ⌊length[A]/2⌋ downto 1
3       do MAX-HEAPIFY(A, i)

上記のアルゴリズムとは異なるケースを生成する他のアルゴリズムはありますか? 入力配列 A={4,1,3,2,16,9,10,14,8,7} の場合、Build-Heap は A={16,14,10,8,7,9,3,2,4 を生成します,1} ヒープ プロパティを満たします。これは、配列からヒープを構築するための最も効率的なアルゴリズムかもしれませんが、ヒープ プロパティを持つ配列の他の順列がいくつかあります。配列のすべての順列を生成し、ヒープ プロパティのテストを実行すると、ヒープ プロパティを持つ配列の 3360 個の順列が得られました。

Count1   16    9    14    4    8    10    3    2    1    7
Count2   16    9    14    4    8    10    3    1    2    7
Count3    16    9    14    4    8    10    2    1    3    7
Count4    16    9    14    4    8    10    2    3    1    7
Count5    16    9    14    4    8    10    7    2    1    3
Count6    16    9    14    4    8    10    7    2    3    1
Count7    16    9    14    4    8    10    7    1    3    2
Count8     16    9    14    4    8    10    7    1    2    3
Count9     16    9    14    4    8    10    7    3    1    2
Count10    16    9    14    4    8    10    7    3    2    1
 ...........................................................

Count3358    16    8    14    7    4    9    10    2    1    3
Count3359    16    8    14    7    4    9    10    3    2    1
Count3360    16    8    14    7    4    9    10    3    1    2

上記のアルゴリズムの出力とは異なる出力を与える、または 3360 の可能な結果のいくつかを与える別のビルドヒープアルゴリズムはありますか?

ビルドヒープを使用して、ヒープ プロパティを満たす配列を取得したら、この配列を使用して他のケースの最大数を生成するにはどうすればよいですか。ヒープのリーフ ノードを交換して、いくつかのケースを生成できます。ヒープ プロパティ テストのすべての順列をチェックせずに、より多くのケースを取得する他の方法はありますか?

配列内の値の範囲とすべての値が異なる場合、ヒープ プロパティを満たす可能性のあるケースの総数について何か言えるでしょうか?

4

2 に答える 2

0

ヒープ構築アルゴリズムは、項目が挿入される順序に影響されます。Build-Heap アルゴリズムでも、同じ要素を別の順序で指定すると、別のヒープが生成されます。

ヒープを構築する場合、部分的に構築された部分は、挿入のたびにヒープ プロパティを維持する必要があることに注意してください。そのため、特定のアルゴリズムによって生成できるさまざまな順列が制限されます。

于 2012-11-04T03:46:39.337 に答える
0

ヒープがあれば、許可された順列の少なくともいくつかを生成するのはかなり簡単です。

ノードは、2 つの子ノードの相対的なサイズを気にしません。したがって、任意のノードの子を交換してから、2 つのうち小さい方をふるいにかけ、そのサブツリーのヒープ プロパティが維持されるようにすることができます (つまり、そのサブノードの 1 つよりも小さい場合は、それを交換します)。そのサブノードを使用して、どちらのサブノードよりも大きい場所に到達するまで、または配列の最後に十分近く移動してリーフノードになるまで、そのパスを下って同じことを続けます。

于 2012-11-17T05:24:15.627 に答える