IT資格用語解説応用情報技術者試験・代表的なアルゴリズム
ヒープソート
更新日:
用語解説
ヒープソートは、データでヒープ（親が子以上の値を持つ完全2分木）を作り、根の最大値を取り出すことを繰り返す整列の方法です。
■ 試験で押さえるポイント
取り出した後は、残りでヒープを作り直します。
計算量は、最悪でもO(n log n)です。
作業領域がほとんどいりませんが、安定な整列ではありません。
■ 過去問での着眼点
ヒープの根が常に最大値になる点を利用します。
例: 最大値を取り出して配列の末尾に置くことを繰り返し、昇順に並べます。