2

これは宿題の質問で、8 要素のバイナリ ヒープには 8 つの比較が必要であることを示すよう求められています。

しかし、次のような例を使用すると、 1 2 3 4 5 6 7 8 ボトムアップとトップダウンのどちらにすべきかわかりません。とにかく、私は両方を試しました。

トップダウン: 8 つのステップで実行しましたが、比較の数を数えると 13 になります:S

ボトムアップ：私は7つのステップでそれをやったが、比較の数を数えると10になる：S

ここでアルゴリズムを試した後、私が得た比較は次のとおりです。

  1. H[L]=8 > H[i]=4
  2. H[L]=8 > H[i]=2、H[r]=5 > H[最大]=8
  3. H[L]=4 > H[i]=2
  4. H[L]=6 > H[i]=3、H[r]=7 > H[最大]=6
  5. H[L]=8 > H[i]=1、H[r]=7 < H[最大]=8
  6. H[L]=4 > H[i]=1、H[r]=5 > H[最大]=4

うーん、比較の数を数えて8つ表示できるようにするにはどうすればよいですか？どの方法を使用しますか (ボトムアップまたはトップダウン)?

4

2 に答える 2

9

受け入れられた答えは間違っていると思います。

ヒープをボトムアップで構築するのは実際には O(n) ですが、これは一般的なケースに適用される上限にすぎません。要素数が 8 の場合など、特定のケースではそれよりもパフォーマンスが向上する可能性があります。以下に、8 つの比較で 8 つの要素のヒープを構築できる少なくとも 1 つの方法を示します。

8 つの要素 {A、B、C、D、E、F、G、H} があり、それらの相対的な順序について何も知らないとしましょう。まず、8 つの要素の任意の 4 つのペアを比較します。このステップの後、4 つの比較を行い、以下に例示するように 4 つの「順序付けられた」ペアができました。

A > B, C > D, E > F, G > H

ここで、1 回の比較で 2 つのペアを N = 4 のツリーにまとめることができることに注意してください。たとえば、最初の 2 つのペアを取得して A と C を比較すると、左下のツリーのいずれかになります ( A > C) または右側のもの (C > A の場合):

    A     |       C 
  C   B   |     A   D
D         |   B

同じプロセスを他の 2 つのペアに適用し、これまでに 6 回の比較を使用して N = 4 のツリーを 2 つ作成します。次のようなものがあります。

    A              E 
  C   B   and    G   F
D              H

A > E1 つの追加の比較で、A と E の間でどちらがより高い順序を持っているかを判断できます。一般性を失うことなく言ってみましょう。これまでに7つの比較を使用しました。最後に、最後の比較左を使用して、A の下の要素 (B と C) 間の順序を決定し、その情報を使用して、左上のツリーを下の 2 つのうちの 1 つに再配置します (B > 左の C、C >右側の B):

 A        |   A     
   B      |     C   
 C   D    |   B   D

最後に、 がすでにわかっているのでA > E、以下に示すように、2 つのツリー (E をルートとするツリーと A をルートとするツリー) を簡単に結合できます。

         A
    E         B
  G   F     D   C
H

これで、8 つの比較で構築された 8 つの要素のヒープができました。うまくいけば、すべてが理解できました。

于 2015-08-15T23:37:59.157 に答える
1

ヒープの構築は、ボトムアップが直線的で、トップダウン (またはインクリメンタル) がO(n log n).

木を描くだけでなく、実際のアルゴリズムに従うようにしてください。あまりにも多くの試験で、きれいな木を描いているのにアルゴリズムに従っていない人がいるのを見てきました。これは通常、誤った結果や非効率などにつながります。木は単なる「アイデア」であり、「方法」ではありません。ここでのメソッドは、実際には配列を使用しています。

編集：ボトムアップはヒープサイズの半分から始まります。したがって、要素 4 と 7 の比較では次のようになります。

Level 3: 4 < 8
Level 2: 3 < 7, 3 < 6
         2 < 5, 2 < 4
Level 1: 1 < 3, 1 < 2

Edit2: 最大ヒープ:

Level 3: 4 < 8 -> Swap 4-8.
Level 2: 3 < 7, 3 < 6 -> Swap 3-7, fix heap down (no-op)
         2 < 5, 2 < 8 -> Swap 2-8, fix heap down:
           2 < 4 -> Swap 2-4, fix heap down (no-op)
Level 1: 1 < 7, 1 < 8 -> Swap 1-8, fix heap down
           1 < 4, 1 < 5 -> Swap 1-5, fix heap down (no-op)
Resulting heap:
          8
      5       7
    4   1   6   3
   2

10回比較します。ですから、あなたの宿題の質問に誤りがあったか、質問の報告が間違っていたと思います。ヒープをボトムアップで構築するということは、正確に比較O(n)するという意味ではありません。n正確な境界については、教科書を確認してください。

于 2011-12-24T21:51:43.913 に答える