This documentation is automatically generated by online-judge-tools/verification-helper
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.fast_heapq import heapify, heappop, heappush, heappushpop, heapreplace
from cp_library.ds.heap.heap_proto import HeapProtocol
class MinHeap(HeapProtocol[_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
_T = TypeVar('T')
_U = TypeVar('U')
def heappush(heap: list, item):
heap.append(item)
heapsiftdown(heap, 0, len(heap)-1)
def heappop(heap: list):
item = heap.pop()
if heap: 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
def heappushpop(heap: list, item):
if heap and heap[0] < item: item, heap[0] = heap[0], item; heapsiftup(heap, 0)
return item
def heapify(x: list):
for i in reversed(range(len(x)//2)): heapsiftup(x, i)
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 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 heappop_max(heap: list):
item = heap.pop()
if heap: item, heap[0] = heap[0], item; heapsiftup_max(heap, 0)
return item
def heapreplace_max(heap: list, item):
item, heap[0] = heap[0], item; heapsiftup_max(heap, 0)
return item
def heapify_max(x: list):
for i in reversed(range(len(x)//2)): heapsiftup_max(x, i)
def heappush_max(heap: list, item):
heap.append(item); heapsiftdown_max(heap, 0, len(heap)-1)
def heapreplace_max(heap: list, item):
item, heap[0] = heap[0], item; heapsiftup_max(heap, 0)
return item
def heappushpop_max(heap: list, item):
if heap and heap[0] > item: item, heap[0] = heap[0], item; heapsiftup_max(heap, 0)
return item
def heapsiftdown_max(heap: list, root: int, pos: int):
item = heap[pos]
while root < pos and heap[p := (pos-1)>>1] < item: heap[pos], pos = heap[p], p
heap[pos] = item
def heapsiftup_max(heap: list, pos: int):
n, item, c = len(heap)-1, heap[pos], pos<<1|1
while c < n and item < heap[c := c+(heap[c]<heap[c+1])]: heap[pos], pos, c = heap[c], c, c<<1|1
if c == n and item < heap[c]: heap[pos], pos = heap[c], c
heap[pos] = item
from typing import Generic
class HeapProtocol(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(HeapProtocol[_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)