Source code for titan_pylib.data_structures.heap.Randomized_meldable_heap

  1from typing import TypeVar, Generic, Iterable, Optional
  2
  3T = TypeVar("T")
  4
  5

[docs]
  6class RandomizedMeldableHeap(Generic[T]):
  7    """併合可能ヒープです。
  8
  9    [Randomized Meldable Heap](https://trap.jp/post/1050/), traP
 10    """
 11
 12    _x, _y, _z, _w = 123456789, 362436069, 521288629, 88675123
 13

[docs]
 14    class Node:
 15
 16        def __init__(self, key: T) -> None:
 17            self.key = key
 18            self.left = None
 19            self.right = None

 20
 21    def __init__(self, a: Iterable[T] = []):
 22        self.root = None
 23        self.size = 0
 24        self._build(a)
 25
 26    def _build(self, a: Iterable[T]) -> None:
 27        a = sorted(a)
 28        if not a:
 29            return
 30        n = len(a)
 31        pool = [self.Node(e) for e in a]
 32        for i in range(len(a)):
 33            if i * 2 + 1 < n:
 34                pool[i].left = pool[i * 2 + 1]
 35            if i * 2 + 2 < n:
 36                pool[i].right = pool[i * 2 + 2]
 37        self.root = pool[0]
 38
 39    @classmethod
 40    def _randbit(cls) -> int:
 41        t = cls._x ^ (cls._x << 11) & 0xFFFFFFFF
 42        cls._x, cls._y, cls._z = cls._y, cls._z, cls._w
 43        cls._w = (cls._w ^ (cls._w >> 19)) ^ (t ^ (t >> 8)) & 0xFFFFFFFF
 44        return cls._w & 1
 45
 46    @classmethod
 47    def _meld(cls, x: Optional[Node], y: Optional[Node]) -> Optional[Node]:
 48        if x is None:
 49            return y
 50        if y is None:
 51            return x
 52        if x.key > y.key:
 53            x, y = y, x
 54        if cls._randbit():
 55            x.left = cls._meld(x.left, y)
 56        else:
 57            x.right = cls._meld(x.right, y)
 58        return x
 59

[docs]
 60    @classmethod
 61    def meld(
 62        cls, x: "RandomizedMeldableHeap", y: "RandomizedMeldableHeap"
 63    ) -> "RandomizedMeldableHeap":
 64        new_heap = RandomizedMeldableHeap()
 65        new_heap.size = x.size + y.size
 66        new_heap.root = cls._meld(x.root, y.root)
 67        return new_heap

 68

[docs]
 69    def push(self, key: T) -> None:
 70        node = RandomizedMeldableHeap.Node(key)
 71        self.root = self._meld(self.root, node)
 72        self.size += 1

 73

[docs]
 74    def pop_min(self) -> T:
 75        res = self.root.key
 76        self.root = self._meld(self.root.left, self.root.right)
 77        return res

 78

[docs]
 79    def get_min(self) -> T:
 80        return self.root.key

 81

[docs]
 82    def tolist(self) -> list[T]:
 83        node = self.root
 84        stack = []
 85        a = []
 86        while stack or node:
 87            if node:
 88                stack.append(node)
 89                node = node.left
 90            else:
 91                node = stack.pop()
 92                a.append(node.key)
 93                node = node.right
 94        a.sort()
 95        return a

 96
 97    def __bool__(self):
 98        return self.root is not None
 99
100    def __len__(self):
101        return self.size
102
103    def __str__(self):
104        return str(self.tolist())
105
106    def __repr__(self):
107        return f"{self.__class__.__name__}({self})"