各ノードの子が常に親より大きくなる（あるいは小さくなる）バイナリ・ヒープを作ってみた。ヒープはソートに使われるほかにも、順序付きキュー（pre-ordered queue）など結構重要な応用があるらしい。順序のあるキューを配列で実現する場合、3つのアプロー…

MyHeapのsiftdownでコードの重複と分岐の分かりづらさが気になったので書き換えてみた。 def siftdown(n) if n * 2 > @n then return elsif n * 2 == @n then if @q[n] > @q[n * 2] then @q[n], @q[n * 2] = @q[n * 2], @q[n] end elsif n * 2 + 1 <= @n the…