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