kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

ALDS1_9_C: Priority Queue

二分ヒープに挿入と取り出しをつけて優先度キューに仕立て上げようという問題
今回は問題文にアルゴリズムの説明はない

ということは、これまでのアルゴリズムを再利用するということかな?
それとも説明するほど難しくはないということ?

一番単純な再利用は毎回build_max_heapを実行することだけど
それではオーダがn^2 になってしまうし

続きを読む

ALDS1_8_C: Binary Search Tree III (続き5)

解説の疑似コードを見る

この問題でgetSuccessorを呼ぶのは必ず子が2つあるときなので、
右に子がいないときのことは考えなくていい気がする
汎用的に次節点を求めるならこう書かないといけないんだろうけど
ていうか考えてなかった

続きを読む

ALDS1_8_C: Binary Search Tree III (続き4)

いろんなケースでちゃんと動くことを確認しようと思ったら
どれだけ書けばいいか見当がつかない

こういう場合コンピュータの中の人に力づくでテストしてもらうっていうのは
どうだろう

続きを読む