併合可能ヒープ (Skew Heap)
(DataStructure/Heap/SkewHeap.py)

• View this file on GitHub
• Last update: 2021-01-14 12:29:07+09:00

概要

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

使い方

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

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

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

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

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

• add(val: int) -> None
  ヒープ内のすべての要素に val を加算する。計算量 $O(1)$

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

Required by

• 最小有向全域木 (Graph/SpanningTree/directed_mst.py)

Verified with

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

Code

class SHNode:
    def __init__(self, val):
        self.l = None
        self.r = None
        self.val = val
        self.add = 0

    def lazy_propagate(self):
        if self.l is not None: self.l.add += self.add
        if self.r is not None: self.r.add += self.add
        self.val += self.add
        self.add = 0


class SkewHeap:
    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 + b.add < a.val + a.add: a, b = b, a
        a.lazy_propagate()
        a.r = self._meld(a.r, b)
        a.l, a.r = a.r, a.l
        return a

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

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

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

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

    def add(self, val):
        self.root.add += val

    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