insert/extract ともに難しいので写経。完全二分木を使いこなすには程遠い理解度、ということがわかりました。 #include <iostream> #include <vector> #include <algorithm> #include <cstdio> using namespace std; const static int INFTY = (1<<30); static vector<int> A(2000000 + 1); static int</int></cstdio></algorithm></vector></iostream>…

buildMaxHeap() と maxHeapify() が問題文に書いてあり、そのままの実装となります。 #include <iostream> #include <cstdio> #include <vector> #include <algorithm> using namespace std; static inline int left(int i) { return 2 * i; } static inline int right(int i) { return 2 * i + 1;</algorithm></vector></cstdio></iostream>…

ヒープ編に突入。今回は問題文通りの実装です。parent, left, right が単純な計算で決定するのが面白いですね。なお、解説の実装では、木の実装が int の配列になっており、自分の実装は無駄な箇所が多々あります。 #include <iostream> #include <cstdio> #include <vector> using nam</vector></cstdio></iostream>…

これはアカンかったです。次節点の探索のところ、ややこしすぎませんか？ あっそういえばポインタの参照を久しぶりに使いました。（rootの入れ替えのところ） #include <iostream> #include <cstdio> #include <memory> using namespace std; struct Node { int key; Node* parent; Nod</memory></cstdio></iostream>…

お仕事でいろいろとやられているので間が空いてしまいました。 今回のお題は前回の内容を引き継いでいるので、あとは探索機能を入れるだけでした。 ※20180417追記：巡回出力のところがバグっていたので直しました #include <iostream> #include <cstdio> #include <memory> using names</memory></cstdio></iostream>…

問題に書いてあった解説どおりの実装です。delete を呼んでないのが気持ち悪いですが、まあ良いでしょう。良くないか。 #include <iostream> #include <cstdio> #include <memory> using namespace std; struct Node { int key; Node* parent; Node* left; Node* right; Node(int key =</memory></cstdio></iostream>…

ちょっと間が空いてしまいました。自力で考えたとっkは、すべての木を復元しようとしたのですが、NGでした。ということでこちらは写経となっております。シンプルな再帰とアルゴリズムを思いつくにはどうしたら良いんでしょうねえ。。 #include <iostream> #include <vector> #</vector></iostream>…

詳細は端折りますが、いろいろと難しく考えすぎて失敗しました。こんなシンプルな方法で巡回になるんですね。。 #include <iostream> #include <vector> using namespace std; struct Node { int id; int parent; int left; int right; Node() : id(), parent(-1), left(-1), r</vector></iostream>…