Cプログラミング
 Computer >> コンピューター >  >> プログラミング >> Cプログラミング

二分ヒープの配列表現

ヒープの順序付けのプロパティに従う完全なバイナリツリーは、バイナリヒープと呼ばれます。 。

バイナリヒープの順序に基づいて、2つのタイプになります-

最小ヒープ ノードの値がその親ノードの値以上であるヒープです。最小ヒープのルートノードが最小です。

最大ヒープ ノードの値がその親ノードの値以下であるヒープです。最大ヒープのルートノードが最大です。

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

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

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

  • iが配列内のノードのインデックスである場合。次に、ノードに関連する他のノードは、配列内で-

    としてインデックス付けされます。

    • 左の子：（2 * i）+1

    • 右の子：（2 * i）+2

    • 親子：（i-1）/ 2

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

二分ヒープの配列表現

1 4 7 8 9 11 12

これで、順序に基づくヒープのタイプについてここで説明できます

  • 最小ヒープ −ルートノードには最小値があります。ノードの値が親ノードの値よりも大きいです。

例-

二分ヒープの配列表現


配列表現-

1 4 7 6 9 10 8

  • 最大ヒープ −ルートノードには最大ノードがあります。ノードの値が親ノードの値よりも小さいです。

例-

二分ヒープの配列表現


配列表現-

11 8 9 6 4 5 1

  1. C++での二項ヒープのメモリ表現

    二項ツリーとは何ですか？ 二項ツリーは順序付けられたツリーデータ構造です。たとえば、B0は単一のノードで構成されますが、Bkとして表される二項ツリーは2つの二項ツリーで構成されます。つまりBk-1は互いにリンクされています。一方の二項ツリーのルートは、もう一方の二項ツリーのルートの左端の子です。二項ツリーは、主に資産または株式の基本的および技術的な分析に使用されます。 二項ツリーのノードは、資産の本質的な価値を表します。投資家や市場の購入者が投資の適切な時期と価値を分析するのに役立ちます。 二項ヒープとは何ですか？ 二項ヒープは、複数の二項ツリーの組み合わせで形成されるデータ構造です。

  2. データ構造における二分木表現

    ここでは、コンピュータのメモリでバイナリツリーを表現する方法を説明します。表現するには2つの異なる方法があります。これらは配列とリンクリストを使用しています。 このようなツリーが1つあるとします- 配列表現は、レベル順の方法を使用して要素をスキャンすることにより、ツリーデータを格納します。したがって、ノードをレベルごとに格納します。一部の要素が欠落している場合は、空白のままにします。上記のツリーの表現は以下のようになります- 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 10 5