cp_library/ds/heap/min_heap_cls.py

• View this file on GitHub
• Last update: 2025-03-30 20:17:47+09:00

Depends on

• cp_library/ds/heap/heap_proto.py

Required by

• cp_library/alg/graph/shortest_path_fn.py
• cp_library/ds/heap/max_k_heap_cls.py

Verified with

• test/atcoder/abc/abc249_f_max_k_heap.test.py
• test/library-checker/graph/shortest_path_min_heap.test.py

Code

import cp_library.ds.heap.__header__
from collections import UserList
from typing import Iterable
from heapq import heapify, heappop, heappush, heappushpop, heapreplace
from cp_library.ds.heap.heap_proto import HeapProtocol
from cp_library.misc.typing import _T

class MinHeap(HeapProtocol[_T], UserList[_T]):
    def __init__(self, iterable: Iterable = None):
        super().__init__(iterable)
        heapify(self.data)
    
    def pop(self): return heappop(self.data)
    def push(self, item: _T): heappush(self.data, item)
    def pushpop(self, item: _T): return heappushpop(self.data, item)
    def replace(self, item: _T): return heapreplace(self.data, item)

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''
from collections import UserList
from typing import Iterable
from heapq import heapify, heappop, heappush, heappushpop, heapreplace
from typing import Generic
from typing import TypeVar
_T = TypeVar('T')

class HeapProtocol(Generic[_T]):
    def pop(self) -> _T: ...
    def push(self, item: _T): ...
    def pushpop(self, item: _T) -> _T: ...
    def replace(self, item: _T) -> _T: ...

class MinHeap(HeapProtocol[_T], UserList[_T]):
    def __init__(self, iterable: Iterable = None):
        super().__init__(iterable)
        heapify(self.data)
    
    def pop(self): return heappop(self.data)
    def push(self, item: _T): heappush(self.data, item)
    def pushpop(self, item: _T): return heappushpop(self.data, item)
    def replace(self, item: _T): return heapreplace(self.data, item)

Back to top page