Randomized_meldable_heap

ソースコード

from titan_pylib.data_structures.heap.Randomized_meldable_heap import RandomizedMeldableHeap

view on github

展開済みコード

  1# from titan_pylib.data_structures.heap.Randomized_meldable_heap import RandomizedMeldableHeap
  2from typing import TypeVar, Generic, Iterable, Optional
  3
  4T = TypeVar("T")
  5
  6
  7class RandomizedMeldableHeap(Generic[T]):
  8    """併合可能ヒープです。
  9
 10    [Randomized Meldable Heap](https://trap.jp/post/1050/), traP
 11    """
 12
 13    _x, _y, _z, _w = 123456789, 362436069, 521288629, 88675123
 14
 15    class Node:
 16
 17        def __init__(self, key: T) -> None:
 18            self.key = key
 19            self.left = None
 20            self.right = None
 21
 22    def __init__(self, a: Iterable[T] = []):
 23        self.root = None
 24        self.size = 0
 25        self._build(a)
 26
 27    def _build(self, a: Iterable[T]) -> None:
 28        a = sorted(a)
 29        if not a:
 30            return
 31        n = len(a)
 32        pool = [self.Node(e) for e in a]
 33        for i in range(len(a)):
 34            if i * 2 + 1 < n:
 35                pool[i].left = pool[i * 2 + 1]
 36            if i * 2 + 2 < n:
 37                pool[i].right = pool[i * 2 + 2]
 38        self.root = pool[0]
 39
 40    @classmethod
 41    def _randbit(cls) -> int:
 42        t = cls._x ^ (cls._x << 11) & 0xFFFFFFFF
 43        cls._x, cls._y, cls._z = cls._y, cls._z, cls._w
 44        cls._w = (cls._w ^ (cls._w >> 19)) ^ (t ^ (t >> 8)) & 0xFFFFFFFF
 45        return cls._w & 1
 46
 47    @classmethod
 48    def _meld(cls, x: Optional[Node], y: Optional[Node]) -> Optional[Node]:
 49        if x is None:
 50            return y
 51        if y is None:
 52            return x
 53        if x.key > y.key:
 54            x, y = y, x
 55        if cls._randbit():
 56            x.left = cls._meld(x.left, y)
 57        else:
 58            x.right = cls._meld(x.right, y)
 59        return x
 60
 61    @classmethod
 62    def meld(
 63        cls, x: "RandomizedMeldableHeap", y: "RandomizedMeldableHeap"
 64    ) -> "RandomizedMeldableHeap":
 65        new_heap = RandomizedMeldableHeap()
 66        new_heap.size = x.size + y.size
 67        new_heap.root = cls._meld(x.root, y.root)
 68        return new_heap
 69
 70    def push(self, key: T) -> None:
 71        node = RandomizedMeldableHeap.Node(key)
 72        self.root = self._meld(self.root, node)
 73        self.size += 1
 74
 75    def pop_min(self) -> T:
 76        res = self.root.key
 77        self.root = self._meld(self.root.left, self.root.right)
 78        return res
 79
 80    def get_min(self) -> T:
 81        return self.root.key
 82
 83    def tolist(self) -> list[T]:
 84        node = self.root
 85        stack = []
 86        a = []
 87        while stack or node:
 88            if node:
 89                stack.append(node)
 90                node = node.left
 91            else:
 92                node = stack.pop()
 93                a.append(node.key)
 94                node = node.right
 95        a.sort()
 96        return a
 97
 98    def __bool__(self):
 99        return self.root is not None
100
101    def __len__(self):
102        return self.size
103
104    def __str__(self):
105        return str(self.tolist())
106
107    def __repr__(self):
108        return f"{self.__class__.__name__}({self})"

仕様

class RandomizedMeldableHeap(a: Iterable[T] = [])[source]

Bases: Generic[T]

併合可能ヒープです。

[Randomized Meldable Heap](https://trap.jp/post/1050/), traP

class Node(key: T)[source]

Bases: object

get_min() → T[source]
classmethod meld(x: RandomizedMeldableHeap, y: RandomizedMeldableHeap) → RandomizedMeldableHeap[source]
pop_min() → T[source]
push(key: T) → None[source]
tolist() → list[T][source]