algorithm - ヒープの親と子を見つけるための方程式の背後にある直感は何ですか?

Question

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

親: i/2

左の子：2i

右の子: 2i + 1

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

Answer 1

重要なのは、要素が幅優先方式で列挙され、インデックスが 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 除算も同じ理由で機能します (剰余は「破棄」されます)。