multiset in Python
Almost anything can be done in combination with [heapq
Insert element with O(logn)
O(1) to obtain the minimum value
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. Size of value range D
Binary search O(logD)
Additions and deletions are O(logD)
Can be both the "kth value" and the "first value over k".
AVL Tree
It is said that "ordered sets are faster in square partitioning" (unconfirmed).
SkipList
---
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.