多重集合 (Multiset)

順序付き多重集合

【Python】平衡二分木が必要な時に代わりに何とかするテク【競プロ】

重複あり集合で、順序関係もあわせて保持するもの。C++のstd::multisetにあたる。

• 挿入(add): \(\mathcal{O}(\log{n})\)

• 削除(discard): \(\mathcal{O}(\log{n})\)

• 最小値の取得(smallest): \(\mathcal{O}(\log{n})\)

Pythonではヒープを用いて簡易的に実装できる。この実装では削除時にキーの存在チェックを行わないことに注意。

import heapq


class Multiset():

    def __init__(self):
        self.addset = []
        self.delset = []

    def add(self, value):
        heapq.heappush(self.addset, value)

    def discard(self, value):
        heapq.heappush(self.delset, value)

    def smallest(self):
        while self.delset and self.addset[0] == self.delset[0]:
            heapq.heappop(self.addset)
            heapq.heappop(self.delset)
        return self.addset[0]

    def is_empty(self):
        return len(self.addset) - len(self.delset) <= 0

S = [3, 7, 3, -2, 4, 5]
mset = Multiset()
for s in S:
    mset.add(s)
print(mset.smallest())
mset.discard(3)
print(mset.smallest())
mset.discard(-2)
print(mset.smallest())
mset.discard(3)
print(mset.smallest())

-2
-2
3
4