min_heap¶
ソースコード¶
from titan_pylib.data_structures.heap.min_heap import MinHeap
展開済みコード¶
1# from titan_pylib.data_structures.heap.min_heap import MinHeap
2# from titan_pylib.my_class.supports_less_than import SupportsLessThan
3from typing import Protocol
4
5
6class SupportsLessThan(Protocol):
7
8 def __lt__(self, other) -> bool: ...
9from typing import TypeVar, Generic, Iterable
10
11T = TypeVar("T", bound=SupportsLessThan)
12
13
14class MinHeap(Generic[T]):
15
16 def __init__(self, a: Iterable[T] = []) -> None:
17 self.a = list(a)
18 self._heapify()
19
20 def _heapify(self) -> None:
21 for i in range(len(self.a) - 1, -1, -1):
22 self._down(i)
23
24 def _down(self, i: int) -> None:
25 a = self.a
26 n = len(a)
27 while i * 2 + 1 < n:
28 u, v = i * 2 + 1, i * 2 + 2
29 if v < n and a[u] > a[v]:
30 u = v
31 if a[i] > a[u]:
32 a[i], a[u] = a[u], a[i]
33 i = u
34 else:
35 break
36
37 def _up(self, i: int) -> None:
38 a = self.a
39 while i > 0:
40 p = (i - 1) >> 1
41 if a[i] < a[p]:
42 a[i], a[p] = a[p], a[i]
43 i = p
44 else:
45 break
46
47 def get_min(self) -> T:
48 return self.a[0]
49
50 def pop_min(self) -> T:
51 res = self.a[0]
52 self.a[0] = self.a[-1]
53 self.a.pop()
54 self._down(0)
55 return res
56
57 def push(self, key: T) -> None:
58 self.a.append(key)
59 self._up(len(self.a) - 1)
60
61 def pushpop_min(self, key: T) -> T:
62 if self.a[0] > key or self.a[0] == key:
63 return key
64 res = self.a[0]
65 self.a[0] = key
66 self._down(0)
67 return res
68
69 def replace_min(self, key: T) -> T:
70 res = self.a[0]
71 self.a[0] = key
72 self._down(0)
73 return res
74
75 def __getitem__(self, k: int) -> T:
76 assert k == 0
77 return self.a[0]
78
79 def tolist(self) -> list[T]:
80 return sorted(self.a)
81
82 def __len__(self):
83 return len(self.a)
84
85 def __str__(self):
86 return str(self.a)
87
88 def __repr__(self):
89 return f"{self.__class__.__name__}({self})"