スポンサーサイト

--.--.-- --:--  スポンサー広告

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

| - | - | ↑ページトップ |




ヒープ Heap

2007.04.10 14:09  データ構造

Priority Queue を効率よく実装するためのデータ構造が ヒープ(heap) です。ヒープもまたデータ構造であり、その論理的構造は完全2分木となっています。完全2分木を1次元配列によって表現するために、木のノードの番号と配列のインデックスを下図のように対応付けます。便宜上インデックスは1から始めます。
ヒープ

木のルートを配列のインデックス1と対応させ(0でないことに注意して下さい)、その左の子を2、右の子を3と対応させます。同様に、各ノードの番号をkとすると、その親、左の子、右の子のインデックスは以下のようになります。

インデックスk
親のインデックスparent = k / 2
左の子のインデックスleft = 2 × k
右の子のインデックスright = 2 × k+ 1


例えば、ノード 5 の
親のノードは parent = k / 2 = 5 / 2 = 2
左の子のノードは left = 2 × k = 2 × 5 = 10
右の子のノードは right = 2 × k + 1 = 2 × 5 + 1 = 11
となります。


ヒープの各ノード(配列の各要素)に、データが格納されます。ヒープにはデータの並びにおける制約があり下図に示すようにMaximum HeapとMinimum Heapの2つのタイプがあります。

ヒープ

上図は整数のデータを格納するヒープを表しています。

マキシマムヒープ Maximum Heap
マキシマムヒープでは上図(左)に示すように、各ノードのキーがその親ノードのキーよりも小さいか等しくなければなりません。ヒープのルートのキーが必ず最大となります。

ミニマムヒープ Minimum Heap
ミニマムヒープは上図(右)に示すように、各ノードのキーがその親ノードのキーよりも大きいか等しくなければなりません。ヒープのルートのキーが必ず最小となります。

マキシマムヒープもミニマムヒープも、データが完全に整列されている必要はありません。左の子と右の子のキーの大小関係に制約はなく、親ノードと子ノードのキーの大小関係にのみ制約があります。

ヒープには、ヒープのユーザ(プログラムやアルゴリズム)がそれに対してなんらかの操作(データの追加・取り出し・入れ替えなど)をした直後に、ヒープの条件(マキシマムヒープまたはミニマムヒープ)を維持するための処理が不可欠となります。この条件を維持するための処理は以下のものを含みます。

  • upHeap()
  • downHeap()


これらの処理を詳しく見てみましょう。ここでは、常にマキシマムヒープの条件を維持することを考えます。


upHeap
下図に示すように、upHeapは起点となるノードcursorの要素を、ヒープの条件を満たすまで木のルートへ向かって上へ移動します。まず1.においてcursorの要素である60が親の要素である8よりも大きくマキシマムヒープの条件を満たしていないので、2.でこれらの要素を交換しcursorを上に移動します。さらに3.においてcursorの要素である60が親の要素である25よりも大きくマキシマムヒープの条件を満たしていないので、4.でこれらの要素を交換し、cursorを上に移動します。5.でマキシマムヒープの条件が満たされたのでupHeapの処理を終了します。

優先順位付きキュー


downHeap
下図に示すように、downHeapは起点となるノードcursorの要素を、ヒープの条件を満たすまで木の葉(子を持たないノード)へ向かって下へ移動します。まず1.においてcursorの要素である6が子の要素である25よりも小さくマキシマムヒープの条件を満たしていないので、2.でこれらの要素を交換しcursorを下に移動します。ここで、cursorの子はノード2(左の子)とノード3(右の子)がありますが、こられのうちキーの値が大きいものを選んで比較します。この場合は25と21を比べ、25の方が大きいので、ノード2を選びます。3.においてcursorの要素である6が子の要素である12よりも小さいので、4.でこれらの要素を交換し、cursorを下に移動します。5.でマキシマムヒープの条件が満たされるのでdownHeapの処理を終了します。

ダウンヒープ


ヒープを使って以下のデータ構造とアルゴリズムを実装することができます。

スポンサーサイト

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。