binomial_heap

ソースコード

from titan_pylib.data_structures.heap.binomial_heap import BinomialHeap

view on github

展開済みコード

  1# from titan_pylib.data_structures.heap.binomial_heap import BinomialHeap
  2from typing import Generic, Iterable, TypeVar
  3from itertools import chain
  4
  5T = TypeVar("T")
  6
  7
  8class BinomialHeap(Generic[T]):
  9    """二項ヒープです。
 10
 11    計算量はメチャクチャさぼってます。
 12    あらゆる操作が :math:`\\theta{(\\log{n})}` です。
 13
 14    ``list`` の代わりに ``LinkedList`` を使用し、``push,meld`` では ``O(1)`` で連結させ、 ``delete_min`` にすべてを押し付けると ``push,meld`` が ``O(1)`` 、``delete_min`` が償却 ``O(logn)`` になるはずです。
 15    """
 16
 17    class _Node:
 18
 19        def __init__(self, key: T) -> None:
 20            self.key = key
 21            self.child: list["BinomialHeap._Node"] = []
 22
 23        def rank(self) -> int:
 24            return len(self.child)
 25
 26        def tolist(self):
 27            a = []
 28
 29            def dfs(node):
 30                if not node:
 31                    return
 32                a.append(node.key)
 33                for c in node.child:
 34                    dfs(c)
 35
 36            dfs(self)
 37            return a
 38
 39        def __str__(self):
 40            return f"_Node({sorted(self.tolist())})"
 41
 42        __repr__ = __str__
 43
 44    def __init__(self, a: Iterable[T] = []) -> None:
 45        self.ptr = []
 46        self.ptr_min = None
 47        self.len = 0
 48        for e in a:
 49            self.insert(e)
 50
 51    @staticmethod
 52    def _link(node1: _Node, node2: _Node) -> _Node:
 53        if node1.key > node2.key:
 54            node1, node2 = node2, node1
 55        node1.child.append(node2)
 56        return node1
 57
 58    def _set_min_node(self) -> None:
 59        self.ptr_min = None
 60        for node in self.ptr:
 61            if not node:
 62                continue
 63            if (self.ptr_min is None) or (self.ptr_min.key > node.key):
 64                self.ptr_min = node
 65
 66    # O(logN)
 67    def push(self, key: T) -> None:
 68        self.len += 1
 69        new_node = BinomialHeap._Node(key)
 70        ptr = self.ptr
 71        if self.ptr_min is None or self.ptr_min.key > key:
 72            self.ptr_min = new_node
 73        for rank, node in enumerate(self.ptr):
 74            if node is None:
 75                ptr[rank] = new_node
 76                return
 77            new_node = BinomialHeap._link(new_node, node)
 78            ptr[rank] = None
 79        ptr.append(new_node)
 80
 81    # O(1)
 82    def get_min(self) -> T:
 83        assert self.ptr_min, "IndexError: find_min from empty BinomialHeap"
 84        return self.ptr_min.key
 85
 86    # O(logN)
 87    def pop_min(self) -> T:
 88        _len = self.len - 1
 89        node = self.ptr_min
 90        new_bheap = BinomialHeap()
 91        new_bheap.ptr = node.child
 92        new_bheap._set_min_node()
 93        self.ptr[node.rank()] = None
 94        while self.ptr and self.ptr[-1] is None:
 95            self.ptr.pop()
 96        self._set_min_node()
 97        self.meld(new_bheap)
 98        self.len = _len
 99
100    # O(logN)
101    def meld(self, other: "BinomialHeap") -> None:
102        self.len += other.len
103        h0, h1 = self.ptr, other.ptr
104        if len(h0) > len(h1):
105            h0, h1 = h1, h0
106        n = len(h1)
107        new_node = None
108        min_node = self.ptr_min
109        if (other.ptr_min) and (min_node is None or min_node.key > other.ptr_min.key):
110            min_node = other.ptr_min
111        for rank in range(n):
112            if rank >= len(h0) and new_node is None:
113                break
114            cnt = (rank < len(h0) and h0[rank] is not None) + (h1[rank] is not None)
115            if new_node:
116                if cnt == 2:
117                    x = new_node
118                    new_node = BinomialHeap._link(h0[rank], h1[rank])
119                    h1[rank] = x
120                elif cnt == 1:
121                    new_node = BinomialHeap._link(
122                        new_node, (h1[rank] if h1[rank] else h0[rank])
123                    )
124                    h1[rank] = None
125                else:
126                    h1[rank] = new_node
127                    new_node = None
128            else:
129                if cnt == 2:
130                    new_node = BinomialHeap._link(h0[rank], h1[rank])
131                    h1[rank] = None
132                if cnt == 1:
133                    if h1[rank] is None:
134                        h1[rank] = h0[rank]
135        if new_node:
136            h1.append(new_node)
137        self.ptr = h1
138        self.ptr_min = min_node
139
140    def tolist(self) -> list[T]:
141        return sorted(chain(*[node.tolist() for node in self.ptr if node]))
142
143    def __len__(self):
144        return self.len
145
146    def __str__(self):
147        return str(self.tolist())
148
149    def __repr__(self):
150        return f"{self.__class__.__name__}({self})"

仕様

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

Bases: Generic[T]

二項ヒープです。

計算量はメチャクチャさぼってます。 あらゆる操作が \(\theta{(\log{n})}\) です。

list の代わりに LinkedList を使用し、push,meld では O(1) で連結させ、 delete_min にすべてを押し付けると push,meld が O(1) 、delete_min が償却 O(logn) になるはずです。

get_min() → T[source]
meld(other: BinomialHeap) → None[source]
pop_min() → T[source]
push(key: T) → None[source]
tolist() → list[T][source]