併合可能永続ヒープ (Persistent Leftist Heap)
(DataStructure/Heap/PersistentLeftistHeap.py)

• View this file on GitHub
• Last update: 2022-01-20 19:40:17+09:00

概要

大きさが $N$ と $M$ のヒープ同士を計算量 $O(\log (N+M))$ で併合可能な永続ヒープ。ヒープの要素は (キー, 値) の組み合わせで表現され、キーの小さい要素が優先度が高い。キーは重複を許す。

使い方

LeftistHeap()
空のヒープを作成する。計算量 $O(1)$

• __bool__() -> bool
  ヒープが空かどうか返す。計算量 $O(1)$

• __lt__(other: LeftistHeap) -> bool
  ヒープ同士をキーの値で比較し、other よりも小さければ True を返す。そうでなければ False を返す。計算量 $O(1)$

• insert(key: int, val: int) -> LeftistHeap
  ヒープに (キー、 値) の組を持つ要素を追加したときのヒープを返す。ヒープの大きさを $N$ とすると、計算量 $O(\log N)$

• find_min -> Tuple[int, int]
  ヒープ内の最小のキーを持つ要素の (キー, 値) の組を返す。計算量 $O(1)$

• delete_min() -> LeftistHeap
  ヒープ内の最小のキーを持つ要素を $1$ つ削除したときのヒープを返す。ヒープの大きさを $N$ とすると、計算量 $O(\log N)$

LeftistHeap.merge(hl: LeftistHeap, hr: LeftistHeap) -> LeftistHeap
ヒープ hl と hr を併合したときのヒープを返す。それぞれのヒープの大きさを $N, M$ とすると、計算量 $O(\log(N+M))$

Required by

• 上位 $k$ 個のウォーク (Graph/misc/k_shortest_walk.py)

Verified with

• TestCase/AOJ/ALDS1_9_C.PersistentLeftistHeap.test.py

Code

class LeftistHeap:
    E = None

    def __new__(cls, *args):
        if cls.E is None:
            cls.E = super().__new__(cls)
        return super().__new__(cls) if args else cls.E

    def __init__(self, rank=0, key=None, value=None, a=None, b=None):
        self.rank = rank
        self.key = key
        self.value = value
        self.a = a
        self.b = b

    def __bool__(self):
        return self is not LeftistHeap.E

    def __lt__(self, other):
        return self.key < other.key

    @staticmethod
    def _make(key, value, a, b):
        if a.rank >= b.rank:
            a, b = b, a
        return LeftistHeap(a.rank + 1, key, value, b, a)

    @staticmethod
    def merge(hl, hr):
        if not hl:
            return hr
        elif not hr:
            return hl
        elif hl.key <= hr.key:
            return LeftistHeap._make(hl.key, hl.value, hl.a,
                                     LeftistHeap.merge(hl.b, hr))
        else:
            return LeftistHeap._make(hr.key, hr.value, hr.a,
                                     LeftistHeap.merge(hl, hr.b))

    def insert(self, key, value):
        new = LeftistHeap(1, key, value, LeftistHeap.E, LeftistHeap.E)
        return LeftistHeap.merge(new, self)

    @property
    def find_min(self):
        if self is LeftistHeap.E:
            raise IndexError("find from empty heap")
        return self.key, self.value

    def delete_min(self):
        if self is LeftistHeap.E:
            raise IndexError("delete from empty heap")
        return self.merge(self.a, self.b)

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page