Interval Heap
(DataStructure/Heap/IntervalHeap.py)

• View this file on GitHub
• Last update: 2021-05-08 17:40:31+09:00

概要

最小値と最大値を同時に管理するヒープ。

使い方

IntervalHeap()
空のヒープを作成する。計算量 $O(1)$

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

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

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

• push(val: int)
  ヒープに val を追加する。計算量 $(\log N)$

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

• pop_max() -> int
  ヒープ内の最大の値を削除してその値を返す。計算量 $(\log N)$

Verified with

• TestCase/unittest/IntervalHeap.unittest.test.py

Code

class IntervalHeap:
    def __init__(self):
        self.hp = []

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

    @property
    def max(self):
        if len(self) == 1:
            return self.hp[0]
        return self.hp[1]

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

    def push(self, val):
        self.hp.append(val)
        k = len(self) - 1
        self._heap_up(k)

    def pop_min(self):
        if len(self) == 0:
            raise IndexError('pop from empty list')
        if len(self) < 2:
            return self.hp.pop()
        self.hp[0], self.hp[-1] = self.hp[-1], self.hp[0]
        res = self.hp.pop()
        k = self._heap_down(0)
        self._heap_up(k)
        return res

    def pop_max(self):
        if len(self) == 0:
            raise IndexError('pop from empty list')
        if len(self) < 3:
            return self.hp.pop()
        self.hp[1], self.hp[-1] = self.hp[-1], self.hp[1]
        res = self.hp.pop()
        k = self._heap_down(1)
        self._heap_up(k)
        return res

    def _heap_down(self, k):
        if k & 1:
            while 2 * k + 1 < len(self):
                chi_k = 2 * k + 3
                if len(self) <= chi_k or self.hp[chi_k - 2] > self.hp[chi_k]:
                    chi_k -= 2
                if chi_k < len(self) and self.hp[k] < self.hp[chi_k]:
                    self.hp[k], self.hp[chi_k] = self.hp[chi_k], self.hp[k]
                    k = chi_k
                else:
                    break
        else:
            while 2 * k + 2 < len(self):
                chi_k = 2 * k + 4
                if len(self) <= chi_k or self.hp[chi_k - 2] < self.hp[chi_k]:
                    chi_k -= 2
                if chi_k < len(self) and self.hp[k] > self.hp[chi_k]:
                    self.hp[k], self.hp[chi_k] = self.hp[chi_k], self.hp[k]
                    k = chi_k
                else:
                    break
        return k

    def _heap_up(self, k):
        if k | 1 < len(self) and self.hp[k & ~1] > self.hp[k | 1]:
            self.hp[k & ~1], self.hp[k | 1] = self.hp[k | 1], self.hp[k & ~1]
            k ^= 1
        while k != 0:
            par_k = ((k >> 1) - 1) & ~1
            if self.hp[par_k] <= self.hp[k]:
                break
            self.hp[par_k], self.hp[k] = self.hp[k], self.hp[par_k]
            k = par_k
        while k != 1:
            par_k = (((k >> 1) - 1) & ~1) | 1
            if self.hp[par_k] >= self.hp[k]:
                break
            self.hp[par_k], self.hp[k] = self.hp[k], self.hp[par_k]
            k = par_k
        return k

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