ヒープの親と子を見つけるアルゴリズムは次のとおりです。
親: i/2
左の子:2i
右の子: 2i + 1
配列表現を紙に描いてみましたが、完全に直感的に理解できるかどうかはわかりません。
ヒープの親と子を見つけるアルゴリズムは次のとおりです。
親: i/2
左の子:2i
右の子: 2i + 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 除算も同じ理由で機能します (剰余は「破棄」されます)。