ヒープ [Heap]

ヒープ^(註)は半順序集合^(註)をツリーで表現したデータ構造です。親ノードは、子ノードよりも小さい(あるいは大きい)か等しいという条件を満たすツリー構造になります。 子の関係に制約はありません。あくまで親子間での制約です。

単にヒープと呼ぶ場合、バイナリツリーとして構成されるバイナリヒープを指すことが多いです。

特徴 - ヒープ プロパティ

親子の関係によってヒープの性質 - ヒープ プロパティ [heap peoperty]^(註)は2種類に分かれます。

最大ヒープ [max-heap property]

親ノードは子ノードより大きいか等しい。

最小ヒープ [min-heap property]

親ノードは子ノードより小さいか等しい。

プロパティによりルートノードは常に最大あるいは最小要素となります。ヒープはこういった特徴から、抽象データ型であるプライオリティ キュー [priority queue] (優先順位付き待ち行列とも呼ばれる)のデータ構造として利用されます。
また、ヒープを用いた整列アルゴリズムに、ヒープソートというものがあります。

実装

ヒープ(バイナリヒープ)は配列を使って実現されます。ツリーの高さは高さ n の要素が使用されるまで、高さ n+1 の要素を作成しません。インデックスを 1 から開始するとノード n の親ノードは n/2、子ノードは 2n と 2n+1でアクセスできます。

親ノードのインデックスを計算する除算 n/2 は小数点以下を切り捨てます。

サンプルコード

C言語

配列で最大ヒープ [max-heap] を作成する関数です。

/* max-heap property */
void insert(int val, int heap[], int counter)
{
    int i = counter + 1;
    while( (i != 1) && (heap[i/2] < val) ) {
        heap[i] = heap[i/2];
        i = i/2;
    }
    heap[i] = val;
}
  

注釈

ヒープ

コンピュータ サイエンスでヒープと言う場合「ヒープ領域」を指すこともありますので間違わないようにしましょう。

半順序集合

リンク: 半順序集合とは

ヒープ プロパティ [heap property]

日本語訳をほとんど見掛けませんが「ヒープ特性」と書かれた文書を目にした事があります。一般的な訳語が無いという判断でこの文書ではカタカナ英語にしています。