テクノロジ系 / アルゴリズムとプログラミング
ヒープソート
半順序木（ヒープ）を使ってデータを整列する、計算量O(n log n)の整列法です。
もう少し詳しく
ヒープソートは、親が子より大きい（または小さい）という性質をもつヒープを作り、根にある最大値（最小値）を取り出して末尾に置く操作を繰り返して整列します。最悪・平均ともに計算量はO(n log n)で安定して速く、追加の作業領域がほとんど不要（その場でソート）です。一方、同じ値の順序が保たれない不安定ソートです。
試験での見方
例：1万件のデータでも、ヒープソートなら最悪でもO(n log n)で安定して整列できます。
計算量O(n log n)と「不安定ソート」である点が問われます。最悪O(n²)になり得るクイックソートとの比較が頻出です。 「ヒープ＝山。一番上（最大）を順にもぎ取る」イメージ。