削除可能 heapq
(expansion/misc/DeletableHeapq.py)

• View this file on GitHub
• Last update: 2023-06-22 23:45:32+09:00

概要

削除可能 heapq です．内部で hashDict を使っているので，hack 対策に rnd() を一様に足してあげると良いかもしれません

使い方

• __init__(lst=None, reverse=False) := lstに要素を指定すると初期の配列を作ってくれます reverse=Trueにすると最大値取得に，Falseにすると最小値取得になります．
• __bool__() := 現在の配列長が1以上かどうかを返します．
• __len__() :=現在の配列長を返します．
• top() := heapqの先頭の要素を返します．要素が1つもない場合，Noneを返します．
• __getitem__(i) := hq[0] で top()と同じものをかえします．hq[1]のように，index番号が0で無いケースは対応してません．
• push(x) := heapqにxを追加します．
• pop() := heapqの先頭の要素を削除し，返り値とします． 要素が1つもない場合，Noneを返します．
• remove(x) := heapqからxを削除します． 削除できた場合はTrueを， 削除できなかった場合($x$が存在しなかった場合)はFalseを返します．

Code

import heapq


class DeletableHeapq:
    def __init__(self, lst=None, reverse=False):
        if reverse:
            self.pm = -1
        else:
            self.pm = 1
        if lst is None:
            self.hq = []
        else:
            self.hq = [self.pm * x for x in lst]

        heapq.heapify(self.hq)
        self.tot = sum(self.hq) * self.pm
        self.cnt = {}
        for x in self.hq:
            self.cnt[x] = self.cnt.get(x, 0) + 1
        self.length = len(self.hq)

    def __bool__(self):
        return bool(self.hq)

    def __len__(self):
        return self.length

    @property
    def sum(self):
        return self.tot

    def top(self):
        if self.hq:
            return self.hq[0] * self.pm
        else:
            return None

    def __getitem__(self, i):
        # 先頭要素にアクセスしたいときのみ
        assert i == 0
        return self.top()

    def push(self, x):
        self.length += 1
        self.cnt[x * self.pm] = self.cnt.get(x * self.pm, 0) + 1
        self.tot += x
        heapq.heappush(self.hq, x * self.pm)

    def pop(self):
        if not self.hq:
            return None
        self.length -= 1
        x = heapq.heappop(self.hq)
        self.cnt[x] -= 1
        self.tot -= x * self.pm
        self._delete()
        return x * self.pm

    def remove(self, x):
        if self.cnt.get(x * self.pm, 0) == 0:
            return False
        self.length -= 1
        self.cnt[x * self.pm] -= 1
        self.tot -= x
        self._delete()
        return True

    def _delete(self):
        while self.hq and self.cnt.get(self.hq[0], 0) == 0:
            heapq.heappop(self.hq)

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 81, in _render_source_code_stat
    bundled_code = language.bundle(
                   ^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/python.py", line 108, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page