ヒープソートとは？

ヒープソートの意味

データからヒープ（親が子より必ず大きい、または必ず小さい木構造）を構成し、根にある最大値または最小値を取り出しては木を再構成する操作を繰り返して整列する方法。最悪でもO(n log n)で、追加の作業領域をほとんど必要としない点が特徴。

ヒープソートの具体例

配列を最大ヒープにすると根が最大値になる。根と末尾の要素を交換して末尾を確定させ、残りを再びヒープに直す。この「取り出して整え直す」を繰り返すと、配列の後ろから大きい順に確定していき昇順に整列される。整え直しは木の高さ分＝log n回の比較で済む。

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

ヒープは「親と子」の大小関係しか保証せず、左右の子の間や兄弟間の順序は決まっていない。二分探索木のように「左<親<右」が成り立つと誤解しやすい。また不安定なソートである点も問われる。

ヒープソートと関連する用語

• ヒープ