listen to my digital heartbeat.

　競技プログラミング系の問題を解いていて、時々「優先度付きキュー」みたいなものが必要になる場合がある。

　ソート済みの配列みたいなものがあって、そこに1つずつデータを（適切な位置に）追加していきたいのだが、挿入ソートみたいにやるとO(n)の計算量がかかってしまうのでそれは嫌だ、というようなケース。

　プログラミング言語によっては実装済みコードがライブラリにあるのだろうが、僕が普段使っているRubyにはないっぽい（いや、ないワケないとは思うのだが…）。そこで、ヒープを使って自分で書いてみた。

　…と言うのはウソで、「ヒープ」そのものをパッと書けなかったのだが…（涙）。

def upheap value
　@heap << value
　node, parent = @heap.length - 1, (@heap.length - 1) / 2
　while parent != 0 && @heap[parent] > @heap[node]
　　@heap[parent], @heap[node] = @heap[node], @heap[parent]
　　node, parent = parent, parent / 2
　end
end

def downheap
　value, @heap[1] = @heap[1], @heap[-1]
　@heap.pop
　node = 1
　while true
　　child, val = nil, nil
　　child, val = node * 2, @heap[node * 2] if @heap[node * 2]
　　child, val = node * 2 + 1, @heap[node * 2 + 1] if @heap[node * 2 + 1] && val > @heap[node * 2 + 1]
　　break if val.nil? || @heap[node] <= val
　　@heap[child], @heap[node], node = @heap[node], val, child
　end
　return value
end

@heap = [nil]
[5, 3, 7, 9, 0, 2].each{|v| upheap v}
arr = []
while @heap != [nil]
　arr << downheap
end
p arr
#=> [0, 2, 3, 5, 7, 9]

　こんな感じかなぁ…。もうちょっとスッキリ書きたいものだが…。

　ここでは、値を「昇順」で取り出しているが、赤字にした3か所の不等号を逆向きにすれば「降順」で取り出すことが出来る。


※　html上でインデントさせるために全角スペースを入力しています。そのため、このままコピーして実行してもエラーが出ると思います（全角スペースを半角スペースなりタブなりに置換すれば動きます）。