# Approaching Heapsort via Lazy Mergesort
[toc]
---
# はじめに: ヒープソート未だに良くわからん
ヒープソートが分からずとも生きていけます。
しかし
[稲葉さんほどの人に、ヒープソート最強一番好きなアルゴリズムです](http://www.kmonos.net/wlog/123.html#_2257111201)、
と言わしめる力が、どこにあるのか、ふとした瞬間に気になります。
ヒープソートの何がそれほど良いのか、そこそこ長い間の疑問だったのですが、
[元ネタセクション](#元ネタ)に書いた道筋でヒープソートに接近して、
この説明なら分かる！！という感情が芽生えたので、書き散らかします。
ヒープソートってイマイチ分かった気がせんのよなあという
個人的な苦手意識の最大部分は
* 大体の教科書に登場する理由がいつまでたっても掴めない（他にある多くのソートアルゴリズムを押しのけて出現するほどの「良さ」があるのか？）
で、具体的には
* 配列 から ヒープ木を作る、といった次の瞬間に、配列「の中に」仮想木を作るプレゼンは、単に昔の教科書的なあるあるなのか、それとも他の理由があるのか？
* アルゴリズムそのものから、セジウィックの[（古い方の）Algorithms](https://www.amazon.com/gp/product/0201066726/) みたいな、あの辺のクラシカルな本でのクイックな最適化を想起します。
* ところで、このバージョンのセジウィック本は、表紙がソートのvisualizeっぽくなっててカッコいいんですよね〜
* ヒープ木のtopと末尾を入れ替えるアドホック感がヤバい
* 他の比較ソートは基本的に一種類の計算の繰り返しで通ってるけど、ヒープソートはそういう感じが薄い
とか、この辺なんですかね。
自分のことながら、いざ言語化するとやはりあやふやな感じなので、
どこが掴みきれてないのかという事自体が、良く分かっていないようです。
本エントリでは、上記の薄っすらとした疑問に
全てに説明をつける面白い方法でヒープソートに接近します。
# 元ネタ
この文書には元ネタがあります。
* https://twitter.com/pi8027/status/1457230574490316803
* http://logic.cs.tsukuba.ac.jp/~sakaguchi/slides/haskell-day-2021.pdf
* https://www.youtube.com/watch?v=haZl-q6mfyk&t=5281s
リンク先のスライドとトークでは、
Lazy Mergesort（マージソートをHaskellで実装したもの）が
partial sorting---$N$要素リストのソート結果の先頭$k$個の要素が$O(N + k \log N)$で取れる---
になるというトピックを扱っています。この部分はスライド前半の内容で、後半はより進んだ話題です。
最初このスライドを紹介してもらった時に、スライドのプレゼンで既に面白いなあ!!! と思ったのですが、もう少し考えていたら、
<div style="text-align: center; font-weight:bold; font-style: oblique; font-size: 110%">
Lazy Mergesortって、ヒープソートにもみえへん？!
</div>
という考えに至ったのでこの文章を準備しました。
強調しておきますが、**このスライドを見ていなかったら、この文章は思いついていません**。ぜひ元のスライドもご覧ください。
しかし一度そういう lazy mergesort ~ heapsort という視点を獲得してググってしまうと、ブログの記事なんかが出てきて
* https://apfelmus.nfshost.com/articles/implicit-heaps.html
やっぱり同じようなことを考える人はいるもんですねえ。
ですのでここで一旦、新規性はない、ということを強調しておきますが
とはいえ色々調べてせっかく書いたので公開しよう、という記事です。
# 本エントリの構造
全体像を見失わないように、ここで内容を圧縮紹介します。
1節では、ヒープソートの良い性質であるpartial sorting性に着眼します。
幾らヒープソートっぽいものを作っても、
この要件が満たせてないとヒープソートとは呼ばないという覚悟です。
というか目標です。
その目標を設定した上で
* 2節でHaskellでマージソートを実装 (lazy mergesort) します。
でもこのままだと $O(N \log N)$ です。
* 3節で問題点を克服して、トーナメントソートという
$O(N + k \log N)$時間ソートを作ります。
* 4節でトーナメントソートのちょっとした問題点を述べます。
* 5節でこの問題点を克服する形で、ヒープソートを導入します。
* 6節ではヒープソート最強！！を補足します。
全体的には、マージソートぐらいの
1. 「まあこれなら分かるかな」という所からスタートして、
2. ヒープソートのような「イマイチ分かった気がしない」所に到着できると、
3. 道を歩いている間に色々分かってくるかな？
というストーリーですね。
# 1. 要件: ヒープソートのPartial Sorting性
今回は与えられた配列 $A$ を昇順に並べることを考えます。つまり
$$
B = \text{heapsort}(A)
$$
について、$B[0] \leq B[1] \leq \cdots$ です。
ヒープソートの時間計算量に関する以下の性質が大事です:
* 長さ $N$ の配列を $O(N \log N)$ で $B$ に変形する。
* 先頭から $k$ 個 $B[0], B[1], \ldots, B[k-1]$ は $O(N + k \log N)$ で取り出せる。
* なので 全体の$N$個は $O(N + N \log N)$ で取り出せる
* かつ、$O$-記法的に $O(N \log N)$ と一致
* これが出来るソートアルゴリズムを、[partial sorting](https://en.wikipedia.org/wiki/Partial_sorting)と呼ぶらしいです。
$k$ 個が $O(N + k \log N)$ で取り出せるというところが、そう言われると面白いところです。
というのも、
* クイックソートやマージソートのような他の「比較ソート」で全体をソートして
（ヒープソートも比較ソートです）
* それから先頭$k$個を取り出すというのが脳裏に浮かびます
* しかし、そうするとまず全体のソートで $O(N \log N)$ かかる
* 比較ソートのlower boundに関する議論はいつも何ひけばよいのかわからないのですが、大体の教科書にあります。
* [これはググって出てきたPDF](https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lecture7.pdf)
ということになって、他の比較ソートだと $O(N + k \log N)$ を超えてくるので要注意です。
ここからは、頑張って $O(N + k \log N)$ で$k$個取り出せるソートを目指します。
<details>
<summary>でもO(N)ソートってあるやん……?と思った方はここを開いてください </summary>
いやいや、全体を$O(N)$でソートするアルゴリズムを使えば良いじゃん
という話があります。バケツソートとか基数ソートとかProxmapソートとか。
これはその通りで、それで良いと思います。
ただこの辺の計数ソートはkeyのデータ型に応じて
追加で必要になるメモリがすごいことになったりするので、
まあ比較ソートはその辺も穏やかなのでトレードオフかなという気がします。
例えば、文字列の配列を「辞書式順で」ソートしたい、という時にこれをバケツソートとか基数ソートしようとすると、
結局$p$進展開しているみたいな感じのデータなので、
辞書式順の場合はバケツへのマッピングが結構大変になる気がするんですよね。容量を増やせば何とかなりそうなんですが、ケチろうとすると一気に難しくなりそう。
</details>
# 2. Haskellでマージソート
ヒープソートじゃなくてマージソートの話をします。それもHaskellを使って。
なんでHaskellなんだよ、については
* 遅延評価がある言語なら何でも良くて、自分が楽に書けるのがHaskell
* 「リスト」ベースで話を見ておくと、後で「配列」に転換するんですが、その時に「配列の存在そのもの」に対してカタルシスを感じられる
というあたりが理由です。
じゃあ遅延評価はどこで使うのか？というと、
* 普通にマージソートをリストに適用すると一気に全部ソートしてしまって、
そこで$O(N \log N)$かかるのでもうダメ
* でも、遅延評価があると必要なところだけ「勝手に」計算してくれて何とかなるよ
というところで使います。
「何とかなるよ」……というのは結論が先に来ていますが、
非常に素朴に書いたマージソートではやっぱり$O(N \log N)$なので、
問題点を見て、それを改善して $O(N + k \log N)$ にします。
## 普通のマージソートの問題点
普通のマージソートのコードをドバっと載せておきます。
当たり前のことをやっているだけで、
このコードについて後で虚をついてびっくりさせることもしないので、
あまり細かく考えずに「まあマージソートってこんなんだわな」
ぐらいでサクッと見てもらえれば大丈夫です。
```haskell=
{-# LANGUAGE ViewPatterns #-}
import Debug.Trace(trace)
import Data.List
import System.Environment(getArgs)
type Val = Int -- 全順序が入っている型なら何でも良いです
-- 下のsplitで使います
view :: Val -> Val
view x = trace ("<" ++ show x ++ ">") x
-- split n list は、
-- list を 長さnの前半部分 α と残り β に
-- 分割 list = α ++ β する関数です。
-- 標準ライブラリにもあるような関数ですが
-- 後で定義に立ち入りたいのでわざわざ書いています。
split :: Int -> [Val] -> ([Val], [Val])
split 0 xs = ([], xs)
split 1 ((view -> x):xs) = ([x], xs) -- viewはここで使っているのですが
split n ((view -> x):xs) = (x:ys, ys') -- 意味は後で説明します
where
(ys, ys') = split (n-1) xs
-- ２つのソート済みリストを合併して
-- １つのソート済みリストにする関数です。
merge :: [Val] -> [Val] -> [Val]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys) =
if x < y then
x : merge xs (y:ys)
else
y : merge (x:xs) ys
-- mergesort L N で 長さN の リストL をマージソートする関数です。
-- なんでリストの長さをいちいち渡すかと言うと
-- リストへのアクセス回数を気にしている以上は、
-- 中で毎回length Lを呼び出したくないからです。
mergesort :: [Val] -> Int -> [Val]
mergesort x 1 = x
mergesort x n =
let
left_len = n `div` 2
(left, right) = split left_len x
left' = mergesort left left_len
right' = mergesort right (n - left_len)
in
merge left' right'
-- 長さnのリスト [n, n-1, n-2, ..., 1]
-- を作ってソートさせる関数です。
msort n = mergesort (reverse $ [1..n]) n
-- コマンドライン引数で数字nを受け取り
-- head $ msort n を実行するmain関数で、
-- ソートした結果から最小の値をとるだけです。
main = do
arg <- getArgs
putStrLn $ show $ head $ msort (read $ head arg)
```
早速ですが、この`msort`はヒープソートの時間要件である
「最初の$k$個は$O(N + k \log N)$で取り出せる」
が満たせて**いない**ことを確認します。
具体的には、最初の1個目を取り出すだけの計算で、$O(N \log N)$かかります。
`main`関数はソート済みリストから1つ目を取り出す計算をしているのですが、
`split` のところで使っている `view` のおかげで、実行してみると
```bash=
$ ghc mergesort.hs
$ ./mergesort 8
<8>
<8>
<8>
<7>
<7>
<6>
<6>
<5>
<4>
<4>
<3>
<2>
```
こんな感じで、 `head $ msort [8, 7, ..., 2, 1]` する間に、
`split`によってどの要素が何回アクセスされたか分かるようになっています。
まず8に三回アクセスして、7に二回アクセスして……という感じです。
繰り返しますが、`split`で発生したリストへのアクセスだけを表示しています。
8が3回、7が2回、6が2回、5が1回、4が2回、3が1回、2が1回 となる理由をみていきます。
最初に
```
[8, 7, 6, 5, 4, 3, 2, 1] -> split 4
[
[*8, *7, *6, *5],
[4, 3, 2, 1]
]
```
として半分の長さにする際に、`split`の定義により、前半4要素へのアクセスが発生します。アクセスごとに `*` をつけていきます。
視覚的にわかりやすくしたいので木を使って書き直させてください:
```
sort [8, 7, 6, 5, 4, 3, 2, 1] -> halve
/---------merge-------\
/ \
sort [*8, *7, *6, *5] sort [4, 3, 2, 1]
```
この図は、入力リストの`sort`は`split 4`してそれぞれ`sort`して`merge`、を木で描いたものです。
`sort`は見かけ上邪魔なので以降では省きますが、本当はあると思ってください。とすると、長さが1になるまで再帰的に半分にされていくので、
```
-> halve
/---------merge------\
/ \
/---merge---\ /--merge--\
/ \ / \
[**8, **7] [*6,*5] [*4, *3] [2, 1]
-> halve
/------------merge----------\
/ \
/---merge---\ /--merge--\
/ \ / \
/merge\ /merge\ /merge\ /merge\
/ \ / \ / \ / \
[***8] [**7] [**6] [*5] [**4] [*3] [*2] [1]
```
全てがサイズ1リストに分割されたときの`*`の個数が、上の実行結果と一致します。
ところで、この洞察によると、長さ$N$のリストについては
* まず最初に $\frac{N}{2}$ のアクセスが走り
* 2つの $\frac{N}{2}$ ができ、
* このそれぞれの前半にアクセスが走るので $2 \cdot \frac{N}{4} = \frac{N}{2}$アクセスが走り
* 4つの $\frac{N}{4}$ ができ ……
というのが分割できなくなるまで $\log N$回 繰り返されるので、合計
$$(N \cdot \log N) / 2$$
アクセスが走ります。このため $O(N + k\log N)$ にはならないんですねえ。
実際にこのオーダーで増えていることは、
```bash=
ghc mergesort.hs
./mergesort 1024 2> mergesort_list_acc.txt
wc -l mergesort_list_acc.txt
```
とかやると(標準エラー出力をリダイレクトしてるのはGHCの[`trace`](https://hackage.haskell.org/package/base-4.15.0.0/docs/Debug-Trace.html)がそっちに出力するからです)
```
5120 out.txt
```
と出るので $(1024 \cdot 10) / 2 = 5120$ で確認できます。
# 3. （Haskellで）トーナメントソート
`mergesort`の、`merge`しはじめる前の、`split`が上手くいっていないことが分かりました。ここを $O(N)$ ぐらいで出来れば良さそうです。
このセクションではこの発想をもとに、$O(N + k \log N)$ソートを作ります。
上の方で木を使って計算全体の状況を表したわけですが、
結局のところ高さが大体 $\log N$ になるように注意しつつ、
mergeを行っているだけです。
なのでここでは、マージソートがトップダウンで木を作っているのに対して
ボトムアップに $O(N)$ 時間で以下のようなトーナメント表を作ります:
```
(m は merge の略記です)
/-------m-------\
/ \
/--m--\ /--m--\
/ \ / \
m m m m
/ \ / \ / \ / \
[x1] [x2] [x3] [x4] [x5] [x6] [x7] [x8]
```
これをやるプログラムが次のトーナメントソートです。
トーナメントソートという名前は新しい名前ではなくて、[既にある名前](https://xlinux.nist.gov/dads/HTML/tournamentSort.html)です。
直感的で良いですよね。
少なくともAPLを作ったIversonによる次のAPL本には書かれているらしいです:
* Kenneth E. Iverson, *A Programming Language*, John Wiley and Sons, 1962.
```haskell=
import Debug.Trace(trace)
import Data.List
type Val = Int -- 全順序が入っている型なら何でも良いです
-- これは [ (m x1 x2), (m x3 x4), ... ] から
-- [ m (m x1 x2) (m x3 x4), ... ] という
-- 左から2つずつ順にmergeして、決勝戦へ近づけるための関数です。
up :: [[Val]] -> [[Val]]
up [] = []
up [xs] = [xs]
up (xs:ys:rest) = (merge xs ys) : (up rest)
-- 対戦カードの文字列化関数
vs x y = "<" ++ show x ++ " vs " ++ show y ++ ">"
-- 単にmergeするだけなんですが
-- traceを使って対戦情報を出しながらmergeしていきます。
merge :: [Val] -> [Val] -> [Val]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys) =
if trace (vs x y) (x < y) then
x : merge xs (y:ys)
else
y : merge (x:xs) ys
-- upを連打してトーナメント表を完成させます。
tournament :: [Val] -> [Val]
tournament l = iter [ [x] | x <- l ]
where
iter [result] = result
iter (x:y:zs) = iter $ up (x:y:zs)
```
**練習問題**: `tournament`でトーナメント表を作る所が$O(N)$で済むことを確認してください（`merge`は実行する必要ないです）。
ヒント: `up`では毎回長さが半分になっていきます。
さて、具体的にどういう順番で対戦が実施されるかというと、
例えば一番小さい値を取り出そうとすると
```
*Main> let sorted = tournament (reverse $ [1..8])
*Main> sorted !! 0
<8 vs 7>
<6 vs 5>
<7 vs 5>
<4 vs 3>
<2 vs 1>
<3 vs 1>
<5 vs 1>
1 <- ちゃんと1が取れています
```
となります。
GHCはこういう戦略で対戦を実際に行っているという証拠なのですが、
以下のように ***lazyに*** 手計算していくと、同じ対戦順が得られます。
```
/------m(1)-----\
/ \
/-m(2)-\ /--m--\
/ \ / \
m(3) m(4) m m
/ \ / \ / \ / \
[8] [7] [6] [5] [4] [3] [2] [1]
sorted !! 0 をしたいので
優勝者が決まっていてほしいのですが、m(1)に誰も居ないので、
まず 左部分木m(2) をなんとかします。
左から見るのは、現在のGHCはleft-to-rightで引数を評価するので合わせています。
ここにも誰もいないので
左におりてm(3)は対戦可能状態なので 8 vs 7 して
その次にm(4)も対戦 6 vs 5 して
次の状態になります
->
/------m1-------\
/ \
/--m--\ /--m--\
7 5 / \
: : m m
[8] [6] / \ / \
[4] [3] [2] [1]
:はconsのつもりです、 e.g., 7:[8] = [7,8]
左側の1回戦が終了しました。
2回戦を行って 7 vs 5 をして
->
/-------m-------\
/ \
5 \
: \
/--m--\ /--m--\
/ \ / \
7 [6] m m
: / \ / \
[8] [4] [3] [2] [1]
今度は右側の最強を決めたいので、同様の手順で
1回戦 4 vs 3, 2 vs 1 と
2回戦 3 vs 1 して
->
/-------m-------\
/ \
5 1
: :
/--m--\ /--m--\
/ \ / \
7 [6] 3 [2]
: :
[8] [4]
決勝戦がようやく出来るので 5 vs 1
->
1
:
/-------m-------\
/ \
5 /--m--\
: / \
/--m--\ 3 [2]
/ \ :
7 [6] [4]
:
[8]
```
この説明で明らかなのですが、参加者が$N$人いる時には、
最初の優勝者が決まるまでに
* 1回戦を行うために結果的に全要素アクセスしているので $N$
* 2回戦では勝ち残った $\frac{N}{2}$ 要素全てにアクセスして $\frac{N}{2}$
* 3回戦では$\frac{N}{4}$にアクセス
* 以降同様……
のリストアクセスを行い、合計で
$$
N (1 + \frac{1}{2} + \frac{1}{4} + \cdots + \frac{1}{2^i} + \cdots)
= 2N
$$
なので、先頭要素をとるのに必要なのは $O(N)$ で済みます。
次に $O(N + \underline{k \log N})$ の 下線部についても問題ないか確認してみます。
例として、`sorted !! 1` すなわち準優勝者を決めるために追加で必要になるリストアクセスを見ますが、これは
```
*Main> sorted !! 1
<3 vs 2>
<5 vs 2>
2
```
たったの2対戦、4アクセスです。こうなるのは王者が抜けたトーナメント
```
/-------m-------\
/ \
5 /--m--\
: / \
/--m--\ 3 [2]
/ \ :
7 [6] [4]
:
[8]
```
について、lazyに次の優勝者を計算してみれば分かります。
俯瞰してみると、
* （最初の）優勝者を決める過程でトーナメントのかなりの部分が計算出来ているので、
* 以降の順位を決定していく際には、対戦相手が決まっていないところを埋めていく
* 上の例だと `5` の対戦相手がいないので、それが決まるところまで計算
という感じです。
トーナメント表の高さを$\log N$と出来ているので、毎回の計算時間は $O(\log N)$ で済みます。
よって、$k$個取り出すのに必要なのは $O(N + k \log N)$ です。
このセクションの締めに強調しておくと<span style="font-size: 150%; color: red;">
Haskellだと
トーナメント表さえ気をつけてO(N)で作れば、
2位以降決めは勝手にO(log N)になる
</span>
というところが良いです。
これ例えばOCamlに移植すると、lazyでないので、1位の値だけ知りたくても全部をどば〜っと計算してくれるので上手くいかないです。
# 4. こんなにうまくいくこと、ある？
なんか上手く行き過ぎている気がする……
というぐらい上手くいっていて気味が悪いのですが、
実はトーナメント表を作るところに若干の疵があります。
* でも優勝者は$O(N)$で求まって、その後も$O(\log N)$で順位付られるというのは揺るぎないので大丈夫です。
この細かい疵を見てみます。
トーナメント表を作るのは関数 `up`
```haskell=
up :: [[Val]] -> [[Val]]
up [] = []
up [xs] = [xs]
up (xs:ys:rest) = (merge xs ys) : (up rest)
```
なのですが、上のような$2^n$ノード数でない場合に、
出来上がる表がマージソートで `split` を使った場合よりやや歪なものとなります。
一例として、$2^n + 1 = 9$ノードの場合を考えてみると `up` では
```
/------------m---------\
/ [x9]
/-------m-------\
/ \
/--m--\ /--m--\
/ \ / \
m m m m
/ \ / \ / \ / \
[x1] [x2] [x3] [x4] [x5] [x6] [x7] [x8]
```
という表が出来てしまいます。とはいえ高さは$O(\log N)$です。
一方で、`split`で半分ずつにする戦略だと
```
[x1, x2, x3, x4, x5, x6, x7, x8, x9]
->
/-----------m---------\
/ \
[x1, x2, x3, x4] [x5, x6, x7, x8, x9]
->
/----------m--------\
/ \
/-----m----\ /---m---\
/ \ / \
[x1, x2] [x3,x4] [x5,x6] [x7,x8,x9]
->
/---------m--------\
/ \
/----m---\ /---m---\
m m m m
/ \ / \ / \ / \
[x1] [x2] [x3] [x4] [x5] [x6] [x7] m
/ \
[x8] [x9]
```
ということで、単に高さ$O(\log N)$ではなく、AVL木になります。
どちらも木の高さは4なのですが、
* 前者は高さ4位置のノードが8つ、高さ1が1つ; 平均3.6
* 後者は高さ4位置のノードが2つ、高さ3が7つ; 平均3.2
ということで後者の方がバランス感が良いです。
この違いは、表の底の方から上まで持ってくる総距離が、
<div style="text-align: center;">`up`で作った場合 > `split`で作った場合</div>
という形で顕れます。
ただ$O$-記法だとどっちも一回あたりは $O(\log N)$ なので差が見えないです。
# 5. 旅の終わり: ヒープソート
ここまでの話をまとめると
+ 高さ $\log N$ の二分木を $O(N)$-時間で作って
+ 後はトーナメントする = lazyにmergeしていく
ことが出来れば、$O(N + k \log N)$ の要件を満たせます。
ですので、二分木を$O(N)$よりも速く作れれば、
その分だけトーナメントソートより速くなる、というのも分かります。
実はこれを達成しているのが**ヒープソート**です。
ただし、
* リストのようなランダムアクセス出来ないデータ構造で$O(N)$で、
尚且つ`split`で作るような、AVL木を作るのは大変そうなので
* ちうか、これって実際に出来るんですかね？
* 「配列」を使ってやります。
## 配列上の木の構築
戦略は次の通り。まず:
```
[x0, x1, x2, x3, x4, x5, x6, x7, x8, x9]
```
という配列から、以下のような
```
/--x0--\
/ \
x1 x2
/ \ / \
x3 x4 x5 x6
/ \ /
x7 x8 x9
```
幅優先的に先頭から値を突っ込んで作った木を爆速で作ります。
これはAVL木です。
ただ、実際に新しいメモリ領域をallocateしてやる必要はなく、
配列 $X$ 上で
* $X[i]$の左の子が$X[2i+1]$
* $X[i]$の右の子が$X[2i+2]$
と思うことにすれば良いです。このindexingで良いことは上の図から分かります。
この段階で既にHaskellで明示的に式木（`up`で作っているような木はしばしばテクニカルには式木/expression treeと呼ばれます）を作っていたのより速いです。
ちょっと速いどころか実際には木を作っていませんので∞倍速いです。
## 合法トーナメント化 = ヒープ化
配列を木として見ることで、上のような平衡木を作れるわけですが、
これは木ではあるもののトーナメント表としてはぶっ壊れています。
例えば
```
x0=9, x1=8, ..., x8=1, x9=0
```
だとすると
```
...
/
x3=6
/ \
/ \
x7=2 x8=1
```
のようなぶっ壊れ状態が散見されるからです。
トーナメント表の直感的な意味合いから、
<div style="text-align: center; font-style: oblique; font-size: 100%">
ある位置のノードは勝ち上がってそこに来ている筈なので
自分より下にいる全ての相手よりも強い
</div>
必要があります。
このぶっ壊れ状態を回復します。
1. 0回戦のところ、すなわち葉（leaf)については自分の下に誰もいないのでOK
2. 1回戦のところで、自分が左か右に負けているなら、より強い方と交換する。
* 今の場合は、`x3 <-> x8` とします。
* `x3 <-> x7` としても、`x8`より弱い`x7`がより上に来ているので、これはダメです。
3. 2回戦部分も同様ですが、交換 `<->` した後に1回戦のところを破壊する可能性があるので、正常になるまで交換していきます。
ノード$X[i]$を正しい位置に持っていくことを$\textit{remedy}(X[i])$と書くことにします。
ちょっくらremedyしまくって、まともなトーナメント表に修正しましょう。
```
9
_/ \_
/ \
8 7
/ \ / \
->6 5<- 4 3
/ \ |
2 1 0
1回戦部分X[3]とX[4]の修正です。
ただこれだとちょい分かりづらいので、
その位置の数字を使って
remedy(6) と remedy(5) と単純に書きます。
=>
9
_/ \_
/ \
8 7
/ \ / \
1 0 4 3
/ \ |
2 6 5
2回戦部分のうちまずremedy(8)します
=>
次のように、8は一番下まで運ばれます
9 9
_/ \_ _/ \_
/ \ / \
0 7 0 7
/ \ / \ -> / \ / \
1 8 4 3 1 5 4 3
/ \ | / \ |
2 6 5 2 6 8
同様にremedy(7)して
9
_/ \_
/ \
0 3
/ \ / \
1 5 4 7
/ \ |
2 6 8
最後に決勝戦修復相当のremedy(9)をして
=>
0
_/ \_
/ \
1 3
/ \ / \
2 5 4 7
/ \ |
9 6 8
無事にトーナメント化
```
さて、トーナメント化できたら自然と優勝者が決まります。
トーナメント化に必要な配列へのアクセス回数はどうなるかというと、
面倒くさいのでここでは $N = 2^n$ の形を考えますが
* 葉が$N/2$ 個あって、修復は不要
* 1回戦位置には$N/4$ 個あって、正しい位置につくまで最大1回の交換
* 2回戦位置には$N/8$ 個あって、正しい位置につくまで最大2回の交換
* 3回戦位置には$N/16$ 個あって、正しい位置につくまで最大3回の交換
* ...
よって
$$
\sum^{\infty}_{k=1} (k-1)\frac{N}{2^k} =
N \sum^{\infty}_{k=1} \frac{k-1}{2^k}
$$
となり収束がどんな感じになるか知りたいのですが、
次のように上から抑えると
$$
\sum^{\infty}_{k=1} \frac{k-1}{2^k} \quad<\quad
\sum^{\infty}_{k=1} \frac{k}{2^k}
$$
* 右項はダランベールの収束判定で収束するとすぐ確認できて、
* さらに、[よくある議論](https://www.quora.com/How-do-you-evaluate-the-sum-of-n-2-n-from-n-1-to-infinity)で「２」に収束する
* なので元々の級数和も2以下に収束する（実際は2に収束します）
と示せます。
既に気づいている方も多いかと思いますが、
**この合法トーナメント化は、これこそがヒープソートのコア操作であるヒープ化(heapify)です**。
この言葉を使うと、最初に優勝者を決めるための全体のヒープ化に必要なのは$O(N)$、ということになります。
あっ、もうヒープソートに突入してたんやあ……という感じなんですが、
２位以降決めが毎回 $O(\log N)$ で出来ることも確認しておきます。
## 2位以降決め
トーナメントソートでやったように、優勝者を除いて、次の勝者を決めます。
例えば
```
?
_/ \_
/ \
1 3
/ \ / \
2 5 4 7
/ \ |
9 6 8
-> ?は空席のつもりです。なので1と3でより強い1が勝って
1
_/ \_
/ \
? 3
/ \ / \
2 5 4 7
/ \ |
9 6 8
となります。次に2と5でより強い2が勝ち
->
1
_/ \_
/ \
2 3
/ \ / \
? 5 4 7
/ \ |
9 6 8
最後に9と6で6が勝ち
->
1
_/ \_
/ \
2 3
/ \ / \
6 5 4 7
/ \ |
9 ? 8
```
直ちに強調するべきこととしては、この計算は
* トーナメントソートで$k \geq 2$-位決めをやっていることと本質的に同じ
* $X[0]$に仮想的な最弱値である `?` を入れて、$\textit{remeady}(X[0])$しているのと同じ
です。
このままでも良いのですが、
もともと$X[0]$に居た要素を保存しておきたい場合に、
追加のスペースが必要となるので、そこが気になります。
しかし、
1. $X[0]$と$X[N-1]$を交換し
2. $X$ を $N-1$要素の配列だと思った上で
3. $\textit{remedy}(X[0])$をしても合法なトーナメントになる
ということに気づけば、つまり
```
0 8 8
_/ \_ _/ \_ _/ \_
/ \ / \ / \
1 3 => 1 3 => 1 3
/ \ / \ / \ / \ / \ / \
2 5 4 7 2 5 4 7 2 5 4 7
/ \ | / \ | / \
9 6 8 9 6 0<-殿堂入り 9 6
```
とすると、
* 優勝者が決まる度に末尾の方に殿堂入りさせるので
元の配列以外の追加spaceが1バイトも必要ない
というメリットがあります。
2位以降決めの$\textit{remedy}$は明らかに$O(\log N)$で済みます。
よって、$k$位までを決めるのに必要なのは$O(N + k \log N)$です。
ミッションコンプリート！！
# 疑問は解決したか？
最初の疑問点が解決できたか見ていきます。
## 疑問1
> 配列 から ヒープ木を作る、といった次の瞬間に、配列「の中に」仮想木を作るプレゼンは、昔の教科書的なあるあるなのか、他の理由があるのか？
今やこれは $O(N)$ でAVL木を作るための非常に頭のキレた実装だと分かります。
上でみた「配列を木とみて速攻でremedyしていく」方法は
実はFloydのTreeSort3というアルゴリズムです:
* *Algorithm 245: TreeSort3*, Robert W. Floyd, CACM '64
* https://dl.acm.org/doi/10.1145/355588.365103
このFloydさんは、勿論あの[Robert Floydさん](https://amturing.acm.org/award_winners/floyd_3720707.cfm)です。なんでも作ってるなあ……
TreeSort3って名前からしてヒープソートじゃねえじゃん！！
と思われるかもしれませんが、
[Wikipediaがヒープソートと言っているので、言っています。](https://en.wikipedia.org/wiki/Heapsort)
余談ですが、追加のメモリを使って、もっとトーナメントソートっぽくする、これまたFloydによるTreeSortというソートもあります:
* *Algorithm 113: TreeSort*, Robert W. Floyd, CACM '62
* https://dl.acm.org/doi/10.1145/368637.368654
これはどんな感じにするかというと、
```
長さ5の配列 x0 x1 x2 x3 x4 をみたら
2*5-1=9の配列を確保して、元配列から値を後ろの方にコピーして
*1 *2 *3 *4 x0 x1 x2 x3 x4 の配列を作り
(*1 *2 *3 *4はallocateした時に入ってる値で
このあと上書きするので中身は何でも良いです)
これは木で捉えると
___*1__
/ \
_*2_ _*3_
/ \ / \
*4 x0 x1 x2
/ \
x3 x4
となり、配列の後ろから2つずつみて、
親位置により強い方を入れる操作を繰り返して
___x4__
/ \
_x4_ _x2_
/ \ / \
x4 x0 x1 x2
/ \
x3 x4
（今は xA の A が大きい方が強いとします）
という状況を作ります。
で、2位を決める時には(remedyではなく)
x4がもと居た所に最弱値?を入れて
___x4__
/ \
_x4_ _x2_
/ \ / \
x4 x0 x1 x2
/ \
x3 ?
?からrootに向かうパスだけで対戦を行っていきます。
なので各値はオリジナル位置も覚えていないといけないです。
```
TreeSort3は、TreeSortの後発なのですが、「あるソートアルゴリズム」に触発されたと論文でも書いている通り、個人的にはTreeSort3の方が余りにも上手くいっている感が強くて好きです。
「あるソートアルゴリズム」については下の疑問3の部分で見ます。
## 疑問2
> ヒープ木のtopと末尾を入れ替えるアドホック感がヤバい
これは既にみちゃいましたが、優勝者を殿堂入りさせた後に、次の勝者を決める部分の処理の話ですね。
入れ替えなくても出来るのですが、入れ替えると追加メモリが必要ないというエレガントさです。
## 疑問3
> 他の比較ソートは基本的に一種類の計算の繰り返しで通ってるけど、ヒープソートはそういう感じが薄い
$\textit{remedy}$という一種類の計算しかしていなかったですね。
なんかヒープソートのイメージと違うんだよなあという気がするのですが、
このイメージの出どころはpriority queue（データ構造としてのヒープ）を使った
ヒープソートの実装に由来すると思います。
* 例えば、[はじめに](#はじめに-ヒープソートとの関わり)でも書いたセジウィックのアルゴリズム本は、データ構造としての二分ヒープでpriority queueを作りつつ、ヒープソートを実装しています。
* このアプローチの教科書は多そう。確かにデータ構造まで含めようとすると省エネで良い。
もっと遡ると、こんにちヒープソートの始祖論文として知られるJ.W. Williamsの論文
* *Algorithm: 232 Heapsort*, J.W. Williams, CACM '64
* https://dl.acm.org/doi/10.1145/512274.512284
では、二分ヒープを事実上使っているソートを実装しています。
Williamsの論文は、「一旦ヒープを作った後」にやることは$\textit{remedy}$なのでそこは同じなのですが、「最初にヒープを作る所」が$\textit{remedy}$を連打しない方法です。
こんにちの言葉で言えば、配列の先頭から順にヒープに「追加」する操作を行います。
この「追加」操作は、下で具体的にみるように「remedy」とは異なる操作です。
```
配列 x0 x1 x2 x3 x4 が与えられたら、メモリの追加はなしで
まず先頭のx0に注目してsingle node tree
x0
としてみて、しかし何もしません（既に自明なヒープなので）
次に x0 x1 まで注目すると
x0
/
x1
という木なので、xAのAが大きい方が強いとすると
x1
/
x0
にするべきなので書き換えて、すると当然配列もx1 x0 x2 x3 x4となり
次は x1 x0 x2まで注目して
x1 x2
/ \ => / \
x0 x2 x0 x1
x2で勝てるところまで交換しながら勝ち進みヒープ化します。
次はx3まで注目して
x2 x3
/ \ / \
x0 x1 => x2 x1
/ /
x3 x0
最後にx4まで注目して
x3 x4
/ \ / \
x2 x1 => x3 x1
/ \ /\
x0 x4 x0 x2
```
なので、「ヒープへの追加」と「remedy」という二種類の操作が
混在しているのがオリジナルのヒープソートですね。
これを「remedy」一種類の操作まで持っていったところが
Floydのすごいところです。TreeSort3の論文で、WilliamsのHeapSortを引用しているので、影響はもちろん受けてい（ると思い）ます。
TreeSort3のprimitive性を良しとするか、
Williamsスタイルを良しとするかは好みの分かれるところです。
というのもWilliamsスタイルは
```
[ array ] -> 入力配列が
[heap|| array ] -> 徐々に左からヒープ化していき
[ heap || array ] -> ...
[ heap ] -> 完全にヒープになったあとは
[ heap || sorted] -> ヒープが減少しつつ
[heap|| sorted ] -> 空きスペースにソート済み要素が入り
[ sorted ] ソートが完成する
```
なるgradualな変形操作とみることができます。
この視点は稲葉さん直伝のものです。
それに
```
arrayからheapへのshift <-dual->
heapからsortedへのunshift(rootと末尾交換)
```
みたくdual（っぽい）操作だと思えば、そこもまた気持ちが良いです。
# おわりに
lazy mergesortを経由して、
* HeapSort by Williamsを解釈することで疑問1と2が個人的に解決できて
* TreeSort3 by Floydを解釈することで、疑問3も個人的に解決できた
ので、非常に気分が良いです。
[はじめに](#はじめに-ヒープソートとの関わり)で書いた最後の疑問
> 大体の教科書に登場する理由が掴めない（他にも沢山ソートアルゴリズムがあるのに）
についても
<div style="text-align: center; font-weight:bold; font-style: oblique; font-size: 150%">
非常に良く出来たアルゴリズムなので<br>
（partial sortingも可能）<br>
むしろ教科書に載っていてほしい<br><br>
</div>
という気持ちです。今では。
当然の様に教科書に載っているので、義務感からうっす〜〜〜く理解はしているものの、
ずっとその程度の理解で止まっていたわけで、
一気にこれぐらいのレベルで見通せるようになると最高ですね。
無理やり覚えたけど身体に馴染んでいない他の基礎的なアルゴリズムがあれば、
今回のような方法で再構築して理解したいですね。
そういうのって何かあるかな〜
Sign in with Wallet
Connect another wallet