0

あか

     1
2          3

有効なヒープですか?

一方

    1
2

ツリーがすべてのレベルでいっぱいになっていないので、そうではありませんか?

または、ヒープの構造プロパティは、レベルの順序で要素間に「ギャップ」がないように、ヒープがちょうど埋められていることのみを指定していますか? 2 番目のヒープも有効なヒープであるということですか?

それとも、ヒープの構造プロパティは、ヒープが FULL であること、つまりすべての親に 0 人または 2 人の子供がいる必要があるだけですか?

そう

           1
       2      3  
   4     7   9   99

そのままの有効なヒープです

           1
       2      3  
   4     7

だがしかし

          1
       2      3  
   4     7   9

?

4

1 に答える 1

1

これは主に用語に関する質問です。ただし、ほとんどの場合、ヒープは根付きツリーとして定義されます。

  1. ルートを除くすべてのノードのキーは、親のキー以上です
  2. すべてのノードには 0、1、または 2 つの子があり、
  3. ツリーはほぼ完全なバイナリ ツリーですが、最後のレベルの可能性があります。最後のレベルは、左から右に入力する必要があります。

したがって、これらは有効なヒープです。

        1                5
     2     3          9     8
   3  6   9         11

そして、これらはそうではありません:

        1                5
     2                9     8
   3                   13  9 10
于 2013-10-08T18:45:42.180 に答える