ヒープソート
リストをヒープに組み替えます。ヒープとは、どの親も子より大きい木のことです。そのあと、最大値を末尾へ移すことを繰り返します。
- Ω(n log n)
- Θ(n log n)
- O(n log n)
- O(1)
- いいえ
- はい
最良: この方法にとって一番楽な入力のとき、リストのサイズ n に応じて時間がどう増えるか。
平均: ふつうの場合に、n に応じて時間がどう増えるか。n² なら値の数が2倍で時間は約4倍。n log n はずっとゆっくり増えます。
最悪: 一番難しい入力での増え方。速さが決して落ちてはいけないときに役立ちます。
メモリ: リストのほかに必要な追加メモリの量。1 なら変数がいくつかだけ、n ならリストのコピー1つ分です。
安定: 同じ値どうしが元の順番を保ちます。レコードを1つの項目で並べ替えるときに大切です。
追加メモリ不要: 2つ目のリストを使わず、リストそのものの中で並べ替えます。
- 比較中
- 移動中
- 位置が確定
試してみましょう: 逆順のリストを選んでください。ヒープ作りでは入れ替えがほとんどなく、そのあと毎回最大値が末尾へ移ります。
仕組み
ヒープはリストの中にそのまま入っています。位置 i の値の子は、位置 2i+1 と 2i+2 にあります。最大値はいつも先頭です。それを末尾と入れ替え、ヒープを1つ小さくしてから直します。並べ終えた部分は右から増えていきます。
向いている場面
最悪の場合でも速さが落ちず、追加のメモリも使えないときに向いています。小さな機器などがその例です。平均するとクイックソートより遅いので、安全策として使われることが多い方法です。