テクノロジ系出題頻度 2/3
ヒープソート
ひーぷそーと
定義
ヒープ構造を利用したソートアルゴリズム。常にO(n log n)でその場ソート可能。
詳細解説
配列をまず最大ヒープに構築し、根（最大値）と末尾要素を交換しヒープサイズを1減らしてヒープ条件を再構築する操作を繰り返す。常にO(n log n)で、追加メモリO(1)のその場ソート。クイックソートよりやや遅いが最悪ケースが保証され、組込みやリアルタイム系で重視される。安定ソートではない。優先度付きキューの応用例の一つで、アルゴリズム学習の重要トピック。
「ヒープソート」が出る問題
関連用語
よくある質問
Q. ヒープソートとは何ですか？
A. ヒープ構造を利用したソートアルゴリズム。常にO(n log n)でその場ソート可能。
Q. 応用情報技術者試験での位置づけは？
A. テクノロジ系の重要用語です。出題頻度は 2/3 （★2）。 中程度の頻度で出題されます。