D-Ary Heap
(DataStructure/Heap/DAryHeap.py)

• View this file on GitHub
• Last update: 2021-01-15 07:30:33+09:00

概要

二分ヒープ (Binary Heap) を D 分木に拡張したヒープ。D = 2 であれば Binary Heap、D = 3 であれば Ternary Heap、D = 4 であれば Quaternary Heap。子 k から親へのアクセスおよび親 k から子へのアクセスを添え字で表現できるため、配列上でヒープをシミュレートできる。

画像は D-Ary Heap の添字の様子。

使い方

DAryHeap(D: int)
D 分木版の空の Binary Heap を作成する。計算量 $O(1)$

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

• min -> int
  ヒープ内の最小の値を返す。計算量 $O(1)$

• push(val: int) -> None
  ヒープに val を追加する。計算量 $O(\log n / \log D)$

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

Verified with

• TestCase/AOJ/ALDS1_9_C.DAryHeap2.test.py
• TestCase/AOJ/ALDS1_9_C.DAryHeap3.test.py
• TestCase/AOJ/ALDS1_9_C.DAryHeap4.test.py
• TestCase/AOJ/ALDS1_9_C.DAryHeap8.test.py

Code

class DAryHeap:
    def __init__(self, D=2):
        self.heap = []
        self.D = D

    def __len__(self):
        return len(self.heap)

    @property
    def min(self):
        return self.heap[0]

    def push(self, val):
        self.heap.append(val)
        idx = len(self) - 1
        par = (idx - 1) // self.D
        while par >= 0 and self.heap[idx] < self.heap[par]:
            self.heap[idx], self.heap[par] = self.heap[par], self.heap[idx]
            idx, par = par, (par - 1) // self.D

    def pop(self):
        if not self:
            raise IndexError('pop from empty heap')
        if len(self) == 1:
            return self.heap.pop()
        res = self.heap[0]
        self.heap[0] = self.heap.pop()
        idx = 0
        while True:
            min_val = self.heap[idx]
            chi = -1
            for i in range(1, self.D + 1):
                tmp_chi = idx * self.D + i
                if tmp_chi < len(self) and min_val > self.heap[tmp_chi]:
                    min_val = self.heap[tmp_chi]
                    chi = tmp_chi
            if chi == -1:
                break
            if self.heap[idx] > self.heap[chi]:
                self.heap[idx], self.heap[chi] = self.heap[chi], self.heap[idx]
            idx = chi
        return res

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