algorithm - 最小ヒープの配列表現

Question

配列のサイズが 20 (0-19) で、マッピングが (i-1)/2 から親への場合。(i-1)/2 のマッピングは、サイズが 13 の最小ヒープを表すことに関連して何を意味しますか?

Answer 1

ダンが言ったように、マッピングは配列のサイズに関係なく同じです。それが役立つ場合は、提供した例のバイナリ ヒープ ツリーを次に示します。2 番目の 70 (レベル 3) は 71 に変更されています。

ツリーを上から下、左から右にトラバースすることで、バイナリ ヒープ配列を取得できます。以下は、以下に示すインデックスを含む結果の配列です。したがって、マッピングをインデックスに簡単に適用して、そこで発生する値を確認し、ツリー レンディションとクロス チェックすることができます。

array  :  10 | 20 | 25 | 60 |  30 | 58 | 71 | 99 | 70 |  82 | 50 | 90 | 85
indices:   0 |  1 |  2 |  3 |   4 |  5 |  6 |  7 |  8 |   9 | 10 | 11 | 12 

これで疑問が解消されることを願っています。