DAA-バイナリヒープ

ヒープにはいくつかの種類がありますが、この章ではバイナリヒープについて説明します。バイナリヒープ*は、完全なバイナリツリーに似たデータ構造です。ヒープデータ構造は、以下で説明する順序付けプロパティに従います。通常、ヒープは配列で表されます。この章では、ヒープを *H で表します。

ヒープの要素は配列に格納されるため、開始インデックスを 1 として、 i ^ th ^ 要素の親ノードの位置は*⌊i/2⌋*で見つけることができます。 i ^ th ^ ノードの左の子と右の子は、位置 2i および 2i + 1 にあります。

バイナリヒープは、順序付けプロパティに基づいて max-heap または min-heap としてさらに分類できます。

最大ヒープ

このヒープでは、ノードのキー値は最上位の子のキー値以上です。

したがって、 _ H [Parent（i）]≥H [i] _

平均ヒープでは、ノードのキー値は最下位の子のキー値以下です。

したがって、 _ H [Parent（i）]≤H [i] _

これに関連して、Max-Heapに関する基本的な操作を以下に示します。ヒープ内の要素の挿入と削除には、要素の再配置が必要です。したがって、 Heapify 関数を呼び出す必要があります。

完全な二分木は、レベル順序走査を使用して要素を格納する配列で表すことができます。

配列 H で表されるヒープ（以下に示す）を考えてみましょう。

レベル順走査を使用して、開始インデックスを 0 と見なすと、要素は次のように配列に保持されます。

Index	0	1	2	3	4	5	6	7	8	…
elements	70	30	50	12	20	35	25	4	8	…

このコンテキストでは、ヒープの操作はMax-Heapに関して表されています。

インデックス i の要素の親のインデックスを見つけるには、次のアルゴリズム Parent（numbers []、i） が使用されます。

Algorithm: Parent (numbers[], i)
if i == 1
   return NULL
else
   [i/2]

インデックス i の要素の左の子のインデックスは、アルゴリズム Left-Child（numbers []、i） を使用して見つけることができます。

Algorithm: Left-Child (numbers[], i)
If 2 *i ≤ heapsize
   return [2* i]
else
   return NULL

インデックス i の要素の右の子のインデックスは、アルゴリズム Right-Child（numbers []、i） を使用して見つけることができます。

Algorithm: Right-Child (numbers[], i)
if 2 *i < heapsize
   return [2* i + 1]
else
   return NULL