ヒープ（Heap）は、木構造（特にすべての葉が左から順に詰まった「完全二分木」）をベースとしたデータ構造で、親子ノード間に「親の値は常に子の値以上（または以下）」という一貫した半順序のルールを持たせたものです。親が子以上であるものを「最大ヒープ（Max-Heap）」、親が子以下であるものを「最小ヒープ（Min-Heap）」と呼びます。このルールにより、ヒープの最上位（根）には常に木全体の「最大値」または「最小値」が位置することになります。ヒープのメリットは、データの追加や最大（小）値の取り出しを行った後に、ヒープのルールを再構築するための計算量がO(log N)と非常に少なくて済む点にあります。メモリ上では、配列を使ってポインタなしでコンパクトに表現することが可能で、インデックス i のノードの子は 2i+1 と 2i+2 という数式で容易にアクセスできます。優先度付きキューの実装や、後述するヒープソートの基盤技術として使用されます。