本履歴

購入した古本の履歴と時々プログラミング

プログラミングコンテストの練習

http://rubygems.org/gems/algorithms
の中からHeapwikipedia:ヒープを使ってみよう!

そもそもHeapってPascalでしか書いたことないし、配列で2分木を表現するBinary Heapで今まで十分だった。
必要な操作は、pushと(最大値/最小値)のpop、sizeくらいかな。
algorithms gemではMerge可能なフィボナッチヒープで実装してくれていて、この実装だとアルゴリズムイントロダクション 第2巻 アルゴリズムの設計と解析手法によれば、Extract_min、DeleteがO(lg n)でそれ以外の操作は鳴らし評価で定数時間とのこと。確かに、Binary HeapでMergeを実装すると配列の合併だから時間かかるよねー(でも、O(N)でできるのかな?O(N*lg n)かかりそう・・・)
でも、Mergeしたくなるシチュエーションが浮かんでこないな。今度調べて見よう。
さて、Rubyで色々書いてみて気づいた点:

  1. pushするときに(key,value)を取り、valueがない場合はvalue=keyになる。
  2. popするときにvalueが返る
  3. keyがheap priority比較対象
  4. priorityが異なるheap同士のmergeがよくわからない。miniheap.merge!(maxheap)の場合。普通そんなことしないんだろうけど。
  5. change_keyはあくまでkeyを変更、keyが2つ以上ある場合の挙動は任意のkeyが変わるから注意

ヒープソート

require"algorithms"

include Containers

minheap=MinHeap.new

srand(42)
N=100

N.times{
	key=rand(1<<30)
	minheap<<key
}

N.times{puts minheap.pop}

あれ?N=10000にすると激遅だなあ。

C extensions (optional, but very much recommended for vast performance benefits)

これだな。Round1までに調べよう。