ヒープとは
ヒープ（Heap）とは、木構造（特に完全二分木）を利用したデータ構造の一種で、「親ノードの値が、子ノードの値よりも常に大きい（または常に小さい）」という親子関係のルールを木全体で保っている状態のことです。このルールを守ることにより、木の一番上（根）には常に「最大値」または「最小値」のデータが配置されることになります。最大（小）値を素早く取り出す用途に適しています。
具体例
「優先度付きのタスク処理システム」において、最も優先度の高いタスク（最大値）をすぐに取り出したい場合にヒープが使われます。根にある最高優先度のタスクをポップし、残りで木を再構築します。
[90] (最優先タスク)
/ \
[85] [70]
/ \
[10] [35]
※どのノードを見ても 親 >= 子 の関係が成り立っています。もう少し詳しく
ヒープ（Heap）は、木構造（特にすべての葉が左から順に詰まった「完全二分木」）をベースとしたデータ構造で、親子ノード間に「親の値は常に子の値以上（または以下）」という一貫した半順序のルールを持たせたものです。親が子以上であるものを「最大ヒープ（Max-Heap）」、親が子以下であるものを「最小ヒープ（Min-Heap）」と呼びます。このルールにより、ヒープの最上位（根）には常に木全体の「最大値」または「最小値」が位置することになります。ヒープのメリットは、データの追加や最大（小）値の取り出しを行った後に、ヒープのルールを再構築するための計算量がO(log N)と非常に少なくて済む点にあります。メモリ上では、配列を使ってポインタなしでコンパクトに表現することが可能で、インデックス i のノードの子は 2i+1 と 2i+2 という数式で容易にアクセスできます。優先度付きキューの実装や、後述するヒープソートの基盤技術として使用されます。
試験でのポイント
試験では、ヒープの条件（完全二分木であり、親ノードの値と子ノードの値の間に一定の大小関係があること）を満たしている木構造の図や配列データを選択させる問題が出題されます。また、ヒープに対して新しい要素を追加した際や、根の要素を取り除いた後に、親子関係を修復（再構築）する「ヒープ化」のプロセスにおけるデータ移動の様子をトレースする問題も出題されるため、アルゴリズムの手順を正しく理解しておく必要があります。
関連する用語
完全二分木（末端以外のすべてのノードが埋まっており、葉が左詰めで配置された二分木）、優先度付きキュー（優先順位の高いものから順に取り出すデータ構造）、ヒープソート（ヒープ構造を利用した高速な整列アルゴリズム）。