併合可能ヒープ (Randomized Meldable Heap)
(DataStructure/Heap/RandomizedMeldableHeap.py)

• View this file on GitHub
• Last update: 2021-01-19 22:36:20+09:00

概要

ヒープ同士を計算量 $O(\log N)$ で併合可能なヒープ。

使い方

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

• min -> int
  ヒープ内の最小の値を返す。計算量 $O(1)$

• push(val: int) -> None
  ヒープに val を追加する。計算量 $\mathrm{expected}\ O(\log N)$

• pop() -> int
  ヒープ内の最小の値を削除してその値を返す。計算量 $\mathrm{expected}\ O(\log N)$

• meld(other: RandomizedMeldableHeap) -> None
  ヒープに other を併合する。計算量 $\mathrm{expected}\ O(\log N)$

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

Depends on

• 乱数生成 (Xorshift) (misc/xorshift.py)

Verified with

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

Code

from misc.xorshift import xorshift32


rand32 = xorshift32()


class RMHNode:
    def __init__(self, val):
        self.l = None
        self.r = None
        self.val = val


class RandomizedMeldableHeap:
    def __init__(self):
        self.root = None

    def _meld(self, a, b):
        if a is None: return b
        if b is None: return a
        if b.val < a.val: a, b = b, a
        if rand32() & 1:
            a.l = self._meld(a.l, b)
        else:
            a.r = self._meld(a.r, b)
        return a

    @ property
    def min(self):
        return self.root.val

    def push(self, val):
        nd = RMHNode(val)
        self.root = self._meld(self.root, nd)

    def pop(self):
        rt = self.root
        self.root = self._meld(rt.l, rt.r)
        return rt.val

    def meld(self, other):
        self.root = self._meld(self.root, other.root)

    def empty(self):
        return self.root is None

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