NISHIO Hirokazu
[Translate]
最小全域木
→
クラスカル法
クラスカル法はO(E log E)
Eが大きすぎて間に合わない時
プリム法
は
フィボナッチヒープ
と組み合わせればO(E+V log V)
素朴な
二分ヒープ
との組み合わせでもO((E+V)log V)になる
Eのソートが線形時間でできればO(E)
→
線形時間ソート
Tweet
Related Pages
Accelerated Hierarchical Density Clustering
線形時間ソート
Luzhiled's memo
PAST3M
プログラミングコンテストチャレンジブック
フィボナッチヒープ
PAST2O
二分ヒープ
クラスカル法
PAST1L
シュタイナー木
codefestival_2016_qualB_c
arc076_b
arc021_4
atcoder scipy
多次元からツリーへ
→
chokudai
×
貪欲法の証明パターン
×
選択肢が少ない方から貪欲
×
マトロイド
×
クラスカル法
×
区間スケジューリング
×
交換しても悪化しない
×
アルゴリズムとデータ構造
×
区間はマトロイドではない
×
abc076b
×
現在が良いほど未来も良い
×
poj3617
×
poj3069
×
ダイクストラ法
×
agc009a
×
arc111
×
abc187
×
arc110c
×
一回り小さい同じ形の問題
×
agc049b
×
abc103d
×
abc023d
×
和の比率の最大化
×
単位時間ジョブスケジューリング問題
×
乱択+貪欲
×
abc171_f
×
離散凸性
→
貪欲法
→
past3
×
past3n
×
past3o
×
past1m
×
past1k
×
最小共通祖先
×
PAST1L
×
クラスカル法
×
past2h
×
past2i
×
past2j
×
past2k
×
最小費用流
×
past2n
×
平面走査法
×
PAST3M
×
巡回セールスマン問題
×
past2m
×
past4m
×
past2l
×
past4n
×
PAST2O
×
past4o
×
past1o
→
PAST過去問練習202012
→
二分ヒープ
×
二項ヒープ
→
二分ヒープの挿入が平均定数時間
→
二分ヒープ
×
データ構造
×
二分ヒープの挿入が平均定数時間
→
二項ヒープ
→
二分ヒープ
×
データ構造
×
ヒープキュー
×
優先度キュー
×
priority_queue
×
ある集合に値が追加削除される。最小の値を取得したい。
×
m個の数がn個の集合を移動する。集合の最小要素を得たい
×
n個の値が更新される、最小値を知りたい
×
ヒープのk番目の値を更新したい
×
中央値
×
best_kの取得
→
heapq
"
Engineer's way of creating knowledge
" the English version of my book is now available on
[Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from
[Scrapbox]
at
11/23/2025, 5:17:40 PM
[Edit]