radix_heap

ソースコード

from titan_pylib.data_structures.heap.radix_heap import RadixHeap

view on github

展開済みコード

 1# from titan_pylib.data_structures.heap.radix_heap import RadixHeap
 2from typing import Generic, TypeVar
 3
 4T = TypeVar("T")
 5
 6
 7class RadixHeap(Generic[T]):
 8
 9    def __init__(self, u: int):
10        self.u = u
11        self.log = u.bit_length()
12        self.lim = (1 << self.log) - 1
13        self.last = 0
14        self._len = 0
15        self.data: list[list[tuple[int, T]]] = [[] for _ in range(self.log)]
16
17    def push(self, key: int, val: T) -> None:
18        assert key <= self.lim
19        self._len += 1
20        self.data[(key ^ self.last).bit_length()].append((key, val))
21
22    def pop_min(self) -> tuple[int, T]:
23        self._len -= 1
24        data = self.data
25        if data[0]:
26            return data[0].pop()
27        for d in data:
28            if not d:
29                continue
30            last = min(d)[0]
31            for elm in d:
32                data[(elm[0] ^ last).bit_length()].append(elm)
33            d.clear()
34            self.last = last
35            break
36        return data[0].pop()
37
38    def __len__(self):
39        return self._len
40
41    def __bool__(self):
42        return self._len > 0
43
44    def __str__(self):
45        a = []
46        for d in self.data:
47            a.extend(d)
48        return str(a)

仕様

class RadixHeap(u: int)[source]

Bases: Generic[T]

pop_min() → tuple[int, T][source]
push(key: int, val: T) → None[source]