ranha さんが、 Approaching Heapsort via Lazy Mergesort という記事を公開していらして、 遅延評価の言語で書くマージソートの計算過程で何が起きているかを見ていくと、 だんだんヒープソートが見えてきた…！という大変面白い記事なのですが、 その話の枕に「稲葉さんというヒープソート大好き人間がいるがいったいどこが良いのか」 という形で私が登場していたので、 思わず何故私がヒープソートが好きであるかをしたためた長文をTwitterのDMで ranhaさんに送りつけてしまいましたという経緯があります。 元ネタの @pi8027 さんの発表 が公になったのに合わせてranhaさんの記事も公開されたみたいなので、 自分の脳内出力もついでにここに書き留めておこうかと思いました。 お二方のように技術的にしっかりした話ではないので、ほぼお気持ち表明です。
編集しようかと思いましたが、なんか勢いで書いている感じが面白い気もするのでコピペしてしまえ。
正直なところ、なぜヒープソートが面白いか理論立ててまとめようとしたことはないので、関連文献的なものはないです。ないですが、とりあえず以下になんで自分が面白いと思っているのか垂れ流しておこうと思います。２点あります。
(1) ソートが、より単純な操作に還元されているので、ソートについてわかった気になる。 つまり「最大値を取る」という単純な操作を繰り返せばよいという還元がなされているので、よい。
マージソートのmerge操作やクイックソートのpartition操作はそこまで還元されている感を感じない…のはなんでかというと、つまりこの辺が今回のranhaさんやpiさんの話と重なるんじゃないかと思うんですが、実際に行われている操作を見ると結局「最小値を取る」の繰り返しを巧妙に計算木の中に埋め込みつつもやっていると見ることができて、ただそれが陽に分出されていない。そこに不満があります。
もちろん、ただ最大値を取る操作の繰り返しにバラしただけではいわゆるselection sortになってしまって遅いわけですが、そこでヒープという賢いデータ構造で殴れば解決するという発想が素晴らしいところで、ソートという複雑な問題を全体としてごっちゃに効率的に解くのではなく、まず単純な問題にバラしてから単純な問題を各個撃破するのでもoptimalな計算量に到達できるというのが、「そこで何が起きているのか」をより深くわかれてよい。
ソートとは全然関係ないんですが、自分が昔やった研究 https://doi.org/10.1016/j.tcs.2010.05.026 とかはそういう方向で、これで提案したアルゴリズムは低レイヤーでの動きを見るとやっていることは完全に既存の https://doi.org/10.1145/602220.602222 と一致するんですが、木オートマトンによるクエリの実装を、全体として謎のスマートなアルゴリズムで解くのではなく、自明なボトムアップの集合演算に還元してから、適切なデータ構造で集合演算の表現を殴りつけてやると十分に速くなるという形にすることで遙かに見通しがよくなっていると思っています。
(2) 二点目としては、配列の中をin-placeに操作する実現がエレガントすぎませんかというのがあって、つまりこのアルゴリズムは、元の配列、ヒープ、ソート済み配列という３つのデータ構造を操るわけですが、メモリレイアウトを見ると
[----------Array-------]だったのが
[---Heap---][--Array---]が
[----------Heap--------]になって
[-Heap-][-SortedArray--]から
[-----SortedArray------]という動きをしていて、単一のデータ構造をin-placeにこねまわしながら実現する類の話ではなくて、３つのデータ構造をメモリに完全に無駄なく配置して操るのが格好良くないですがという話で、
これはなにか概ね妄想ですが
- Array.pop: L- (左から減らすの意)
- Array.pop: R- (右から減らすの意)
- Array.push: L+
- Array.push: R+
- Heap.add: R+
- Heap.popmin: R-
- SortedArray.pushmin: L+
- SortedArray.pushmax: R+
- SortedArray.popmin: L-
- SortedArray.popmax: R-
みたいなラベルをつけた依存型でヒープソートのアルゴリズムに R- と L+ の整合が取れていることを要請するような型システムで型がつくので完全にin-placeで実現ができているみたいな説明が可能だと思っているのですが、そういう方向で一般に任意のアルゴリズムをin-place化可能かどうか考える理論の礎になりそうなあまりに綺麗にはまりすぎている感じが好きですというのがあります。
こういう方向の研究は実際にあってもおかしくないと思うのでちゃんと探したらなんかあるかもしれません。
というわけでした。