Radix Heap
(DataStructure/Heap/RadixHeap.py)

• View this file on GitHub
• Last update: 2021-01-22 20:25:28+09:00

使い方

RadixHeap(LIMIT: int)
格納可能な最大値 LIMIT を指定した空のヒープを作成する。計算量 $O(\log \mathrm{LIMIT})$

• __len__() -> int
  ヒープの大きさを返す。計算量 $O(1)$

• push(val: int) -> None
  ヒープに val を追加する。ただし、最後に pop した値よりも小さな値は入れられない。計算量 $O(\log \mathrm{LIMIT})$

• pop() -> int
  ヒープ内の最小の値を削除してその値を返す。計算量 $O(\log \mathrm{LIMIT})$

Required by

• ダイクストラ法 (Radix Heap) (Graph/ShortestPath/dijkstra_radix.py)

Verified with

• TestCase/AOJ/GRL_1_A.RadixHeap.test.py

Code

class RadixHeap:
    def __init__(self, LIMIT):
        self.LIMIT = LIMIT
        self.vals = [[] for i in range(LIMIT.bit_length() + 1)]
        self.size = 0
        self.last = 0

    def __len__(self):
        return self.size

    def push(self, key, val):
        if key > self.LIMIT:
            raise RuntimeError(f'A pushed value {x} must be no more than {self.LIMIT}')
        if self.last > key:
            raise RuntimeError(f'A pushed value {x} must be not less than the last poped value')
        self.size += 1
        self.vals[(key ^ self.last).bit_length()].append((key, val))

    def pop(self):
        if self.size == 0:
            raise IndexError('pop from empty heapq')
        if not self.vals[0]:
            i = 1
            while not self.vals[i]:
                i += 1
            self.last = min([key for key, _ in self.vals[i]])
            for key, val in self.vals[i]:
                self.vals[(key ^ self.last).bit_length()].append((key, val))
            self.vals[i] = []
        self.size -= 1
        return self.vals[0].pop()

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page