バイナリヒープの配列表現

ヒープの並べ替えプロパティに従う完全なバイナリ ツリーは、バイナリ ヒープと呼ばれます。

バイナリ ヒープのソート方法に応じて、バイナリ ヒープは 2 つのタイプに分類できます。

最小ヒープは、ノードの値がより大きいヒープです。またはその親ノードの値と同じです。最小ヒープのルート ノードは最小です。

最大ヒープ は、ノードの値がその親ノードの値以下であるヒープです。最大ヒープのルート ノードが最大になります。

バイナリ ヒープの値は通常、配列として表されます。バイナリ ヒープの配列表現は次のとおりです。

• ルート要素のインデックスは 0 です。

• i が配列内のノードのインデックスの場合、そのノードに関連する他のノードのインデックスは次のとおりです:

  • 左の子: (2 *i) 1

  • 右の子: (2*i) 2

  • #親ノード: (i-1)/ 2

上記の配列表現ルールを使用すると、ヒープを配列として表現できます。

147891112ここで、ソートベースのヒープのタイプについて説明します。

• 最小ヒープ - ルートノードは最小値を持ちます。ノードの値が親ノードの値より大きいです。

#例:

##配列表現:

#14 8最大ヒープ

7

6

9

10

- ルート ノードには最大値があります。ノードの値は親ノードの値より小さいです。

• #例:

##配列表現:

#11

8

96 1

4

5

以上がバイナリヒープの配列表現の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。