Pythonにmultisetが欲しいという意見がよくある e.g. ABC170 E だいたいのことがheapqとの組み合わせでできる
-
- O(logn)で要素の挿入
- O(1)で最小値の取得
-
heapqとdict(ハッシュテーブル)の組み合わせ heapq+dict
- Pythonでmultisetの代用ができるデータ構造 - Tsuboの競プロブログ
- O(logN)で要素の挿入、削除
- O(1)で要素の存在確認、最小値の取得
- 二分探索ができない
-
二分探索
-
「順序付き集合は平方分割が速い」らしい(未確認
-
SkipList