テクノロジ系出題頻度 3/3
ヒープ
ひーぷ
定義
親と子の間に大小関係の制約を持つ完全二分木。最大値・最小値の取得がO(1)。
詳細解説
最大ヒープは親≥子、最小ヒープは親≤子という制約を持つ完全二分木。配列で表現でき、ノードiの子は2i+1と2i+2、親は(i−1)/2でアクセスできる。挿入と削除はO(log n)、最大/最小取得はO(1)。優先度付きキューの実装、ヒープソート、ダイクストラ法やプリム法の補助構造として利用。動的メモリ管理のヒープ領域とは別概念で混同注意。フィボナッチヒープなど派生も多い。
「ヒープ」が出る問題
関連用語
よくある質問
Q. ヒープとは何ですか？
A. 親と子の間に大小関係の制約を持つ完全二分木。最大値・最小値の取得がO(1)。
Q. 応用情報技術者試験での位置づけは？
A. テクノロジ系の重要用語です。出題頻度は 3/3 （★3）。 頻出のため確実に押さえておきましょう。