CS6.006 Problem Set 2を解く
問題はこちら
今回は大問2のコーディングの部分のみ。 時間あったら大問1のrecursion treeの話も追記します。
- Pythonプロファイラを使ってボトルネックを特定する問題。プロファイラを使う点で実用的。 プライオリティキューが実装されていて、最小値をとってくる関数がO(n)の線形探索として実装されているので、 heapを使って正しくO(1)の操作に直しましょうという問題。
ヒープはPythonのListで実装してある。 実装するべきメソッドは、
find_min() append() pop()
である。
append()した時、pop()した時にListをきちんとheapify(ヒープ化)する必要があるが、 - 前者はappendされた要素を親と入れ替えるように、(上にむかって木を登るイメージ) - 後者はpop()されたrootに末尾の要素を入れ、その末尾と子供を比較して入れ替えるように(下に向かって木を降りるイメージ) の2通りでheapifyする必要がある。 (これ賢くしたら一元化できるのでしょうか？)
上に向かうheapifyは親要素と比べて入れ替えることを再帰で繰り返せば良いので簡単。 下に向かうheapifyは、右の子がOutOfIndexのとき(つまりまだ無いとき)を場合分けして記述しないといけないので注意。
正解実装だと、heapを表すListの先頭にNoneが入っていて、インデックスを1から始めるようにしている。 こっちのほうが親インデックスなどを求める時楽なのだろうか？
