double_ended_heap¶
ソースコード¶
from titan_pylib.data_structures.heap.double_ended_heap import DoubleEndedHeap
展開済みコード¶
1# from titan_pylib.data_structures.heap.double_ended_heap import DoubleEndedHeap
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 Generic, Iterable, TypeVar
10
11T = TypeVar("T", bound=SupportsLessThan)
12
13
14class DoubleEndedHeap(Generic[T]):
15 """
16 - [両端優先度付きキューのInterval-Heap実装](https://natsugiri.hatenablog.com/entry/2016/10/10/035445)
17 - [Double-ended priority queue(wikipedia)](https://en.wikipedia.org/wiki/Double-ended_priority_queue)
18 """
19
20 def __init__(self, a: Iterable[T] = []) -> None:
21 """構築します。
22 :math:`O(n)` です。
23
24 Args:
25 a (Iterable[T], optional): 構築元の配列です。
26 """
27 self._data = list(a)
28 self._heapify()
29
30 def _heapify(self) -> None:
31 n = len(self._data)
32 for i in range(n - 1, -1, -1):
33 if i & 1 and self._data[i - 1] < self._data[i]:
34 self._data[i - 1], self._data[i] = self._data[i], self._data[i - 1]
35 k = self._down(i)
36 self._up(k, i)
37
38 def add(self, key: T) -> None:
39 """``key`` を1つ追加します。
40 :math:`O(\\log{n})` です。
41 """
42 self._data.append(key)
43 self._up(len(self._data) - 1)
44
45 def pop_min(self) -> T:
46 """最小の要素を削除して返します。
47 :math:`O(\\log{n})` です。
48 """
49 if len(self._data) < 3:
50 res = self._data.pop()
51 else:
52 self._data[1], self._data[-1] = self._data[-1], self._data[1]
53 res = self._data.pop()
54 k = self._down(1)
55 self._up(k)
56 return res
57
58 def pop_max(self) -> T:
59 """最大の要素を削除して返します。
60 :math:`O(\\log{n})` です。
61 """
62 if len(self._data) < 2:
63 res = self._data.pop()
64 else:
65 self._data[0], self._data[-1] = self._data[-1], self._data[0]
66 res = self._data.pop()
67 self._up(self._down(0))
68 return res
69
70 def get_min(self) -> T:
71 """最小の要素を返します。
72 :math:`O(1)` です。
73 """
74 return self._data[0] if len(self._data) < 2 else self._data[1]
75
76 def get_max(self) -> T:
77 """最大の要素を返します。
78 :math:`O(1)` です。
79 """
80 return self._data[0]
81
82 def __len__(self) -> int:
83 return len(self._data)
84
85 def __bool__(self) -> bool:
86 return len(self._data) > 0
87
88 def _parent(self, k: int) -> int:
89 return ((k >> 1) - 1) & ~1
90
91 def _down(self, k: int) -> int:
92 n = len(self._data)
93 if k & 1:
94 while k << 1 | 1 < n:
95 c = 2 * k + 3
96 if n <= c or self._data[c - 2] < self._data[c]:
97 c -= 2
98 if c < n and self._data[c] < self._data[k]:
99 self._data[k], self._data[c] = self._data[c], self._data[k]
100 k = c
101 else:
102 break
103 else:
104 while 2 * k + 2 < n:
105 c = 2 * k + 4
106 if n <= c or self._data[c] < self._data[c - 2]:
107 c -= 2
108 if c < n and self._data[k] < self._data[c]:
109 self._data[k], self._data[c] = self._data[c], self._data[k]
110 k = c
111 else:
112 break
113 return k
114
115 def _up(self, k: int, root: int = 1) -> int:
116 if (k | 1) < len(self._data) and self._data[k & ~1] < self._data[k | 1]:
117 self._data[k & ~1], self._data[k | 1] = (
118 self._data[k | 1],
119 self._data[k & ~1],
120 )
121 k ^= 1
122 while root < k:
123 p = self._parent(k)
124 if not self._data[p] < self._data[k]:
125 break
126 self._data[p], self._data[k] = self._data[k], self._data[p]
127 k = p
128 while root < k:
129 p = self._parent(k) | 1
130 if not self._data[k] < self._data[p]:
131 break
132 self._data[p], self._data[k] = self._data[k], self._data[p]
133 k = p
134 return k
135
136 def tolist(self) -> list[T]:
137 return sorted(self._data)
138
139 def __str__(self) -> str:
140 return str(self.tolist())
141
142 def __repr__(self) -> str:
143 return f"{self.__class__.__name__}({self})"
仕様¶
- class DoubleEndedHeap(a: Iterable[T] = [])[source]¶
Bases:
Generic[T][両端優先度付きキューのInterval-Heap実装](https://natsugiri.hatenablog.com/entry/2016/10/10/035445)
[Double-ended priority queue(wikipedia)](https://en.wikipedia.org/wiki/Double-ended_priority_queue)