multiset in Python

There is a common opinion that we want multiset in Python e.g. ABC170 E. Almost anything can be done in combination with [heapq

• heapq

  • Insert element with O(logn)
  • O(1) to obtain the minimum value

• Combination of heapq and dict (hash table) heapq+dict.

  • Data structures that can substitute multiset in Python - Tsubo’s Competitive Pro Blog
  • O(logN) to insert or delete elements
  • O(1) to check existence of element and get minimum value
  • No bifurcation search.

• dichotomous search

  • If you are willing to pre-sort, bisect.
    • The kth value is only read. o(1)
    • First place over k” is RIGHT, “first place over k” is LEFT
  • I want a fixed kth value → heapq.
    • Summary of data structures for fast kth value retrieval - BIT on binary search, equilibrium binary search tree, etc. - Qiita
    • Fennic tree BIT
    • Size of value range D
    • Binary search O(logD)
    • Additions and deletions are O(logD)
      • Compressing D with coordinate compression is effective
    • Can be both the “kth value” and the “first value over k”.
  • equilibrium binary tree
  • RBST
  • AVL Tree
    • https://juppy.hatenablog.com/entry/2019/02/26/python_AVL木_配列ver_競技プログラミング_Atcoder_

• It is said that “ordered sets are faster in square partitioning” (unconfirmed).

  • https://nagiss.hateblo.jp/entry/2019/06/04/220541
    • https://atcoder.jp/contests/abc140/submissions/7482671

• SkipList

  • https://atcoder.jp/contests/arc033/submissions/14718760

• C - Data Structure

• data structure

---

This page is auto-translated from /nishio/Pythonでmultiset using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.