cp_library/ds/heap/min_heap_cls.py

• View this file on GitHub
• Last update: 2025-08-24 20:27:05+09:00

Depends on

• cp_library/ds/heap/heap_base_cls.py
• cp_library/ds/heap/heapify_fn.py
• cp_library/ds/heap/heappop_fn.py
• cp_library/ds/heap/heappush_fn.py
• cp_library/ds/heap/heappushpop_fn.py
• cp_library/ds/heap/heapreplace_fn.py
• cp_library/ds/heap/heapsiftdown_fn.py
• cp_library/ds/heap/heapsiftup_fn.py

Required by

• 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.__header__
from typing import Iterable
from cp_library.misc.typing import _T
import cp_library.ds.__header__
import cp_library.ds.heap.__header__
from cp_library.ds.heap.heapify_fn import heapify
from cp_library.ds.heap.heappop_fn import heappop
from cp_library.ds.heap.heappush_fn import heappush
from cp_library.ds.heap.heappushpop_fn import heappushpop
from cp_library.ds.heap.heapreplace_fn import heapreplace
from cp_library.ds.heap.heap_base_cls import HeapBase

class MinHeap(HeapBase[_T]):
    def __init__(self, iterable: Iterable = None): self.data = list(iterable) if iterable else []; 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 typing import Iterable
from typing import TypeVar

_S = TypeVar('S'); _T = TypeVar('T'); _U = TypeVar('U'); _T1 = TypeVar('T1'); _T2 = TypeVar('T2'); _T3 = TypeVar('T3'); _T4 = TypeVar('T4'); _T5 = TypeVar('T5'); _T6 = TypeVar('T6')



def heapsiftup(heap: list, pos: int):
    n, item, c = len(heap)-1, heap[pos], pos<<1|1
    while c < n and heap[c := c+(heap[c+1]<heap[c])] < item: heap[pos], pos, c = heap[c], c, c<<1|1
    if c == n and heap[c] < item: heap[pos], pos = heap[c], c
    heap[pos] = item

def heapify(x: list):
    for i in reversed(range(len(x)//2)): heapsiftup(x, i)

def heappop(heap: list):
    item = heap.pop()
    if heap: item, heap[0] = heap[0], item; heapsiftup(heap, 0)
    return item

def heapsiftdown(heap: list, root: int, pos: int):
    item = heap[pos]
    while root < pos and item < heap[p := (pos-1)>>1]: heap[pos], pos = heap[p], p
    heap[pos] = item

def heappush(heap: list, item):
    heap.append(item)
    heapsiftdown(heap, 0, len(heap)-1)

def heappushpop(heap: list, item):
    if heap and heap[0] < item: item, heap[0] = heap[0], item; heapsiftup(heap, 0)
    return item

def heapreplace(heap: list, item):
    item, heap[0] = heap[0], item; heapsiftup(heap, 0)
    return item
from typing import Generic

class HeapBase(Generic[_T]):
    def peek(heap) -> _T: return heap.data[0]
    def pop(heap) -> _T: ...
    def push(heap, item: _T): ...
    def pushpop(heap, item: _T) -> _T: ...
    def replace(heap, item: _T) -> _T: ...
    def __contains__(heap, item: _T): return item in heap.data
    def __len__(heap): return len(heap.data)
    def clear(heap): heap.data.clear()

class MinHeap(HeapBase[_T]):
    def __init__(self, iterable: Iterable = None): self.data = list(iterable) if iterable else []; 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