二分ヒープとは図で学ぶ

二分ヒープの概念についてまとめます。

2分ヒープ(Binary Heap)は、図のように木の各接点に割り当てられたキーが
一つの配列の各要素に対応した完全二分木で表された構造のことです。
下記の図が2分ヒープを表したものです。

                   [1]
                   25

          [2]               [3]
          12                ９

    [4]        [5]    [6]          [7]
     6          8      5            4

 [8]   [9] [10]
  3     2    1

この図を配列で表すと以下のようになります。

[1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
25  12   9   6   8   5   4   3   2   1

2分ヒープを配列で表す

図では、2分ヒープを1次元配列で表しています。
2分ヒープを表す配列をA、2分ヒープのサイズをHとすると、
A[1,...,H]に2分ヒープの要素が格納されます。

木の添え字を1から、説点の添え字iが与えられた時の各々にアクセスするには

親[i] = floor(i / 2)(床関数)
左の子[i] = 2 * i
右の子[i] (2 * i ) + 1

で表すことができます。

maxヒープとminヒープ

2分ヒープの各説点のキーは、次に上げるヒープの条件を保つように格納されます。

maxヒープ条件
各節点のキーがその親のキー以下

minヒープ条件
節点のキーがその親のキー以上

図であげた2分ヒープはmaxヒープになります
親子関係のみに大小関係があり、兄弟間に制約はありません。