データ構造

木

根- ノードの一番上
ノード- まる
辺- 線
葉- ノードの末端
二分木-　子のノードが2個以下

順序キュー

キューに似ているが、キューの中で優先順位が早いものが一番早く出る構造。
ヒープのデータ構造を使ってできている場合が多い。
配列やリストだと削除と追加に時間がかかるため、二分木のヒープがよく使われる。

ヒープ

木を用いて子は親より必ず小さいということがポイントである。
ノードが追加される場合、葉の最後となるところに配置させる。
値が親より小さい場合、その関係を逆転させる。先の条件が合わないことろまで繰り返す。
削除ではノードを削除し、根を葉の最後に入れ替えて子が親より小さいことがなくなるまで逆転させる。

union find 木

グループ分けを管理するデータ構造
併合と判定がポイントである。
１から5までの数字があるとする。
１と2を連結させて、2と3を連結させる。これが併合である。
次の判定では3の親は2だが2の親は1であることが分かっている。
union find 木では再帰を用いて根の探索を行う。これが判定である。
これによって2と3は同じ親を持つことになる。
また、5の親は4に設定した場合、1，2，3と4，5は別の木であることが分かる。