読者です 読者をやめる 読者になる 読者になる

情報は力ではない

VimとかC++とかCUDAとか。

Heap sort

Twitterで友達が「ヒープ考案した人、すごい」と言っていたので、誰なのか気になって調べた。
wikipediaによるとJ. W. J. Williamsという方がヒープソートと一緒に考案したそうだ。

Heapsort - Wikipedia, the free encyclopedia

詳しくは1964年に出版された"Algorithm 232: Heapsort"という記事に載っているっぽい。

また、ヒープソートはRobert W. Floyd先生が1962年に出した"Algorithm 113: Treesort"に記述されているTreesortの改良版のらしい。さらにFloyd先生はヒープソートを改良してTreesort 3というアルゴリズムを考案したようだ。Treesort 3に関しては1964年に出た"Algorithm 245: Treesort 3"に詳しく載っている。この記事はネットで拾えたのでリンクしておく。

http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/FloydHeap1964.pdf

"Treesort => Heapsort=> Treesort 3"という流れは、このサイトに載っていた。

ヒープソートにはこういう歴史?があり、50年以上に渡って使われているんだなあという小学生並みの感想を持った。

ちなみに、Robert W. Floyd先生はワーシャル・フロイド法で有名なFloyd先生です。