併合可能ヒープ (Pairing Heap)
(DataStructure/Heap/PairingHeap.py)

• View this file on GitHub
• Last update: 2021-09-13 00:09:16+09:00

概要

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

使い方

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

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

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

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

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

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

Verified with

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

Code

class PHNode:
    def __init__(self, val):
        self.val = val
        self.chi = []


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

    def _meld(self, nd1, nd2):
        if nd1 is None:
            return nd2
        elif nd2 is None:
            return nd1
        if nd1.val > nd2.val:
            nd1, nd2 = nd2, nd1
        nd1.chi.append(nd2)
        return nd1

    def _merge_pairs(self, ndlist):
        newlist = []
        for i in range(len(ndlist) // 2):
            newlist.append(self._meld(ndlist[i * 2], ndlist[i * 2 + 1]))
        if len(ndlist) % 2 == 0:
            nd = None
        else:
            nd = ndlist[-1]
        for other in newlist:
            nd = self._meld(nd, other)
        return nd

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

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

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

    def pop(self):
        val = self.root.val
        self.root = self._merge_pairs(self.root.chi)
        return val

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

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