ヒープとは？

ヒープの意味

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

ヒープの具体例

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

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

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

ヒープと関連する用語

• ヒープソート
• 二分探索木（BST）

ヒープが出た過去問

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

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

  要点：ヒープソートは順序木の根から極値を取り出して整列する

  ヒープソートは、未整列部分をヒープ（親子間に大小関係が保たれた順序木）として構成し、根にある最小値または最大値を取り出して整列済み部分へ移す操作を繰り返す方式です。取り出すたびにヒープを再構成するため、計算量は要素数nに対しておおむね n log n となります。他の選択肢はシェルソート、クイックソート、バブルソートの説明です。

  出典：平成28年度 秋期 応用情報技術者試験 午前 問6（IPA）

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

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

  要点：ガーベジコレクションは不要なヒープ領域を自動回収する

  ガーベジコレクションは、動的に確保したヒープ領域のうち、どこからも参照されなくなった領域を自動的に検出して解放し、再び割当て可能にする仕組みです。プログラマが解放を書き忘れても記憶領域が枯渇しにくくなる反面、回収処理の実行中に一時的な停止が起きることがあります。他の選択肢は用語の対応が入れ替わっています。

  出典：平成28年度 秋期 応用情報技術者試験 午前 問16（IPA）

• プログラムの実行時に利用される記憶領域にスタック領域とヒープ領域がある。それらの領域に関する記述のうち、適切なものはどれか。

  正解：サブルーチンからの戻り番地の退避にはスタック領域が使用され、割当てと解放の順序に関連がないデータの格納にはヒープ領域が使用される。

  要点：スタックは後入れ先出し、ヒープは任意順で確保・解放する領域

  スタック領域は後入れ先出しで管理され、サブルーチンの戻り番地や局所変数など、呼出しと復帰に対応して確保・解放されるデータに使われる。一方ヒープ領域は任意の時点で確保と解放ができるため、確保順と解放順が対応しない動的データの格納に使われる。

  出典：令和1年度 春期 応用情報技術者試験 午前 問17（IPA）

• 配列A[1]，A[2]，…，A[n]で、A[1]を根とし、A[i]の左側の子をA[2i]、右側の子をA[2i+1]とみなすことによって、2分木を表現する。このと…

  正解：幅優先探索

  要点：ヒープ形式の配列表現の添字順は幅優先の訪問順

  この配列表現では、添字の小さい順に根、深さ1の全ノード、深さ2の全ノード…と並ぶ。したがって配列を先頭から順に走査することは、根から始めて同じ深さのノードを左から右へ順に訪問することに等しく、幅優先探索と一致する。深さ優先の3種はいずれも部分木を深く潜ってから戻るため、この並びにはならない。

  出典：令和3年度 春期 応用情報技術者試験 午前 問6（IPA）

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

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

  要点：ガーベジコレクションは不要ヒープ領域の自動回収

  ガーベジコレクションは、動的に確保されたヒープ領域のうち、どこからも参照されなくなった領域を自動的に回収して再利用可能にする機能である。JavaやC#などの実行環境が備えており、解放漏れによるメモリリークを防ぐ。

  出典：令和3年度 春期 応用情報技術者試験 午前 問18（IPA）