ヒープソートとは？

詳細解説

ヒープソートは、ヒープと呼ばれる二分木の構造を使って整列するアルゴリズムです。ヒープは、親の値が子の値より常に大きい（または小さい）という条件を満たす木で、根に最大値（または最小値）が来ます。まず、整列したい要素全体からヒープを作り、根（最大値）を取り出して末尾に置き、残りでヒープを作り直すという操作を繰り返して、要素を順に確定していきます。計算量は、データ数をnとして、どのような並びでも平均・最悪ともにO(n log n)で、追加のメモリがほとんど不要です。一方で、同じ値の順序が保たれない（安定でない）という特徴があります。クイックソートは平均では速いものの、最悪時はO(n²)になる点が異なります。シラバスでは、ソートの用語例として、ヒープソートが挙げられています。

FE試験での出題ポイント

• 1ヒープの条件（親と子の大小関係）を説明できるようにする
• 2計算量が最悪でもO(n log n)であることを、他のソートと比べて区別できるようにする
• 3安定なソートかどうかを整理する

関連用語