ヒープソート

ヒープを利用したソート。最悪計算量はO(n log n)。

数列の並び方がどのようであっても、安定した処理時間を持つ。

ヒープソートの手順
1. ソートを始める前に配列をヒープ化する
               87
               │
       ┌───┴───┐
       │              │
       59              67
       │              │
   ┌─┴─┐      ┌─┴─┐
   │      │      │      │
   50      38      54      29
   │      │      │
 ┌┴┐  ┌┴┐  ┌┘
 │  │  │  │  │
 43  35  15  11  ８
  
2. 一番最初の節点(87)と一番最後の節点(8)の値を入れ替え, 一番最後
   の節点の値はソート済みとする
               ８
               │
       ┌───┴───┐
       │              │
       59              67
       │              │
   ┌─┴─┐      ┌─┴─┐
   │      │      │      │
   50      38      54      29
   │      │
 ┌┴┐  ┌┴┐
 │  │  │  │
 43  35  15  11  87
  
3. 木全体を再びヒープ化する
               67
               │
       ┌───┴───┐
       │              │
       59              54
       │              │
   ┌─┴─┐      ┌─┴─┐
   │      │      │      │
   50      38      ８      29
   │      │
 ┌┴┐  ┌┴┐
 │  │  │  │
 43  35  15  11  87
  
4. 2.に戻る. 以下すべての節点がソート済みになるまで続ける.
               11
               │
       ┌───┴───┐
       │              │
       59              54
       │              │
   ┌─┴─┐      ┌─┴─┐
   │      │      │      │
   50      38      ８      29
   │      │
 ┌┴┐  ┌┘
 │  │  │
 43  35  15  67  87

通信用語の基礎知識検索システム WDIC Explorer Version 7.04a (27-May-2022)