ヒープとは？

ヒープの意味

「親の値は必ず子の値以下（または以上）」という条件を満たす完全2分木。根に最小値（最大値）が来るため、優先度付きキューの実装や整列に使える。

ヒープの具体例

ヒープソートは、データからヒープを作り、根の値を取り出しては再構築する操作を繰り返す整列法。計算量は最悪でもO(n log n)。

ヒープは試験でどう引っ掛けられる？

2分探索木と取り違えやすい。ヒープが保証するのは親子間の大小だけで、左右の子の間や兄弟の間には順序が無い。したがって中間順（通りがけ順）に走査してもソート済み列は得られない——それができるのは2分探索木。またメモリの動的確保領域を指す「ヒープ領域」は同名の別概念。

ヒープと関連する用語

• ヒープソート
• 2分探索木

ヒープが出た過去問

• ヒープソートの説明として、適切なものはどれか。

  正解：未整列の部分を順序木にし、そこから最小値を取り出して整列済の部分に移す。この操作を繰り返して、未整列の部分を縮めていく。

  要点：ヒープソートは順序木から最小値を取り出し続ける

  ヒープソートは、未整列部分を親子の大小関係が保たれた順序木（ヒープ）として構成し、根にある最小値（または最大値）を取り出して整列済み部分へ移す操作を繰り返す。取り出すたびにヒープを再構成するため、計算量は最悪でもO(n log n)に収まる。

  出典：平成28年度 秋期 高度共通_午前I試験 am1 問3（IPA）

• プログラム実行時の主記憶管理に関する記述として、適切なものはどれか。

  正解：プログラムが使用しなくなったヒープ領域を回収して再度使用可能にすることを、ガーベジコレクションという。

  要点：GCは参照されなくなったヒープ領域を自動回収する

  ガーベジコレクションは、プログラムが動的に確保したヒープ領域のうち、どこからも参照されなくなった領域を自動的に検出して回収し、再利用可能にする仕組みである。解放漏れによるメモリリークを防げる一方、回収処理のために実行が一時停止することがある。

  出典：平成28年度 秋期 高度共通_午前I試験 am1 問6（IPA）