1

ヒープの親と子を見つけるアルゴリズムは次のとおりです。

親: i/2

左の子:2i

右の子: 2i + 1

配列表現を紙に描いてみましたが、完全に直感的に理解できるかどうかはわかりません。

4

1 に答える 1

4

重要なのは、要素が幅優先方式で列挙され、インデックスが 1から始まる (0 ではなく 1 から始まる) ことです。

    1
   / \
  2   3
 / \ / \
4  5 6  7

例として 3 を取り上げます

2*3   = 6   left child
2*3+1 = 7  right child

少なくとも整数除算を行う言語では、6 と 7 の両方を 2 で割ると 3 になります。

このように番号を付け続けると、直感が働きます。一般に、2 を掛けると常に左の子のインデックスが得られます。右の子は左の子の後継 (+1) です。整数の 2 除算も同じ理由で機能します (剰余は「破棄」されます)。

于 2012-07-15T23:10:19.367 に答える