優先度の高いものから順に取り出すことの出来るコレクションです。挿入順序がどうであれ、優先度の高いものが必ず1番最初に取り出されます。優先度付き待ち行列への値の挿入・取り出しはそれぞれエンキュー・デキューといいます。プッシュ・ポップという名前で実装する場合もあります。ソートを行うのでは余分な労力を裂いていることになります。通常、優先度付き待ち行列は、このヒープを用いて実装されます。使う分野によって結構意味がばらばらです。常に優先度最大の要素を取り出せる状態に保たれているデータ構造のことを指します。ヒープは、概念上は以下のような性質を満たす木構造です(図2に例を示します)。葉(末端のノード)を除いて、必ず子ノードを2つ持つ。親は子よりも必ず大きな値を持つ。以下のような手順で行います(図2の例に対して、値13を挿入する例を図3に示します)。木構造の末端の右端に新しいノードを作る。新しいノードとその親ノードの持つ値を比べて、親の方が小さければ値を入れ替える。2の操作を、親の方が値が大きくなるか、根に達するまで繰り返す。以下のような手順で行います(図2の例に対して、値を取り出す例を図4に示します)。末端右端の要素の値で、根の値を上書きし、末端右端のノードを削除する。新しい(根になった)ノードとその子ノードの持つ値を比べて、子の方が大きければ値を入れ替える。2の際、子ノードが2つある場合は、値の大きい方の子ノードと値を入れ替える。2、3の操作を、親の方が値が大きくなるか、葉に達するまで繰り返す。演算量が必要になるので、ヒープの方が有利。単なる配列を使って実装することができます。(要素の追加・削除が絡むので、実際には「配列リスト」を使う。左上から順に0から始まる番号を付けてみましょう。その様子を図5に示します。各ノードの番号に対して、以下の事がいえます。「配列リスト」をヒープ化できます。ヒープ化されている配列リストに新しい要素を追加する。最大の値を持つ要素を削除するには以下のようにします。ヒープから最大値を削除する。優先度付き待ち行列の実装は簡単です。ヒープ本体となる「配列リスト」を用意します。buffer;}そして、要素の挿入・削除は以下のように行います。