MaxHeapの話
Heapsortというソーティングアルゴリズムがある。
ソーティングアルゴリズムは、クラシックな分野で学ぶのは少々飽きるが、例えばあるニュースサイトで、その週の閲覧数ランキングを取得したいときなどに利用されると身近にあるものだと考えるとちょっと学習意欲が刺激されはしないだろうか？
Heapsortの特徴を堅そうな言葉でかくと
- in-place: ソートは元の配列で侵襲的に行われるのでソートのためのメモリを余計に消費しない
- 最悪計算時間はO( n log n)
など調べればでてくるが、Heapsortは雑に言うと
配列の要素を、ある規則に従った特殊な並び方にして行うトリッキーなMax Selection Sort
である。
そう、Heapsortの実体は、トリッキーなMax Selection Sortである。
Selection sortについては以下の動画がわかりやすい。
このソーティングでは、長さNの配列について、要素N個の中から最大の要素をみつけ、それを配列の最後に配置する。配列の最後は配列済みのものとして、次は要素N−１個の中から最大の要素をみつけ、それを配列の最後から一つ前に配置する。
これを繰り返すソーティングをSelection sortという。
計算時間は、1st phaseにn-1、2nd phaseにn-2,...のようにかかるので、その総和n(n-1)/2 => O(n^2)かかる。
Heapsortは、このアルゴリズムをちょっと工夫して高速にしたものである。
その「ちょっとの工夫」というのは、配列の並び替えのときにある規則をつくることだ。配列Aとすると以下のルールに従うように配列の並び替えを行う。
- A[1] ≧ A[2], A[3]
- A[2] ≧ A[4], A[5]
- A[3] ≧ A[6], A[7]
- ...
- A[i] ≧ A[2i], A[2i + 1]
この操作はMax Selection Sortでの
長さNの配列について、要素N個の中から最大の要素をみつけ
る過程に影響する。上のルールで並び替えると、A[1]が常にその配列の最大の要素となる。この並び替えをPreprocessingと呼ぶことにするとHeapsortは以下の二つのphaseから構成される。
- Preprocessing
- トリッキーなMax Selection Sort
トリッキーなMax Selection Sortというのは、配列の最大の要素を配列の最後にもってきて、配列サイズを1つ減らす操作である。
先ほど説明したように、Preprocessingのあと、n個の要素からなる配列A[1:n]では以下が成立している。
- A[1] ≧ A[2], A[3]
- A[2] ≧ A[4], A[5]
- A[3] ≧ A[6], A[7]
- ...
この配列における最大の要素はA[1]である。
max selection sortにおいて、最大の要素は配列の最後に持ってくるのでA[1]とA[n]をswapする。
最大の要素はA[n]に格納され、扱う配列のサイズを1つ小さくしたA[1:n-1]について次は考える。
A[1:n-1]の配列は、ほとんどmaxheapになっている。なぜなら以下が成立しているからだ。
A[2] ≧ A[4],A[5]; A[3] ≧ A[6],A[7], ...
一つの問題は、A[1] ≧ A[2],A[3]が成立していない。しかしこの問題は簡単に解決される
Heapsortではcomplete binary treeで可視化すると簡単に説明できる。
例えば要素数が9個の配列は以下のように描画できる。
配列を木構造で表現したときに、Mapheapが満たすべきルール（親要素が、その子要素より大きい場合MaxHeap）が満たされてないことが一目瞭然となるので便利である。
違反してしまった要素の配置は、root-heap path（それはO(log n)の計算時間で済む）にそったswapを連続で行うことにより解決できる。
Heapsortでなにがおこっているかをまとめる。
-
- A[i] ≧ A[2i], A[2i + 1]となるように配列を並び替える(これをheapifyという)。この配列はMaxheapと呼ばれる。
-
- 配列の最初と最後の要素を入れ替え、既に正しい位置にある最後の要素を除いたMaxheapをheapifyする。
Heapsortでは、1,2を繰り返していくことで配列の要素が昇順に並び替えられる。
heapsortの例
complete binary treeでの描画を利用してHeapsortで行われることを可視化する。
以下の配列を並び替えるとする。
7,3,2,6,5,8,1,4
要素の側の赤い数字は、heapfyする際の要素検査の順番である。
要素検査の3番目の8を持つ要素はその親要素より大きいのでswapが行われる。
2と８のswapが終わると、後続の検査が行われ、同様に3と６のswapが行われる。
3の交換のち、その子要素4との交換が行われる。
最後に8と7のswapが行われる。
交換終了したもの
これがheapifyの全容である。
配列は以下のように並び替えられた。
8,6,7,4,5,2,1,3
トリッキーなmax selection sortを行う。最大の数字を取り出すときは、最初の要素を配列最後の要素と交換し、配列のサイズを減らす。
3,6,7,4,5,2,1 | 8
|より後ろは並び替え済みの要素である。次は
3,6,7,4,5,2,1 | 8
についてheapifyを行う。
7,6,3,4,5,2,1 | 8
最大のものを取り出すと以下のような配列になる。
１,6,3,4,5,2,1 | 7, 8
ここから、さらに最大の要素を取り出してみる。
あとの工程は省略するが、これを繰り返すと配列の要素が昇順に並び変わる
Discussion