ヒープ（Heap）は、親と子の間に大小のルールを持つ 木構造（木構造、二分木）です。最大値または最小値を、すばやく取り出せるのが特徴です。
| 種類 | ルール | 取り出せる値 |
|---|---|---|
| 最大ヒープ | 親 ≧ 子 | 常に最大値が根にある |
| 最小ヒープ | 親 ≦ 子 | 常に最小値が根にある |
根（一番上）に必ず最大（または最小）が来るため、優先度の高いものから処理する「優先度付きキュー」の実装に使われます。並べ替えの ヒープソート（ヒープソート）の基盤でもあります。
たとえば緊急度の異なる 5 件の依頼を最大ヒープに入れておけば、根を取り出すだけで常に最も緊急のものが得られます。取り出したあとも木を組み直すだけで、次に緊急なものが根に来ます。
試験では ヒープは「親子の大小関係を保ち、最大／最小をすぐ取り出せる」点が問われます。優先度付きキューやヒープソートと結びつけて押さえましょう。
