cp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub kobejean/cp-library

:heavy_check_mark: cp_library/ds/heap/max_heap_cls.py

Depends on

Required by

Verified with

Code

import cp_library.ds.heap.__header__
from collections import UserList
from typing import Iterable
from cp_library.ds.heap.heapq_max_import import heapify_max, heappop_max, heappush_max, heapreplace_max, heappushpop_max
from cp_library.ds.heap.heap_proto import HeapProtocol
from cp_library.misc.typing import _T

class MaxHeap(HeapProtocol[_T], UserList[_T]):
    def __init__(self, iterable: Iterable[_T] = None):
        super().__init__(iterable)
        heapify_max(self.data)
    def pop(self): return heappop_max(self.data)
    def push(self, item: _T): heappush_max(self.data, item)
    def pushpop(self, item: _T): return heappushpop_max(self.data, item)
    def replace(self, item: _T): return heapreplace_max(self.data, item)
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''
from collections import UserList
from typing import Iterable
from typing import TypeVar
_T = TypeVar('T')
def heappop_max(heap: list[_T], /) -> _T: ...
def heapsiftdown_max(heap: list[_T], root: int, pos: int): ...
def heapsiftup_max(heap: list[_T], pos: int): ...
def heapsiftdown(heap: list[_T], root: int, pos: int): ...
def heapsiftup(heap: list[_T], pos: int): ...

from heapq import (
    _heapify_max as heapify_max, 
    _heappop_max as heappop_max, 
    _siftdown_max as heapsiftdown_max,
    _siftup_max as heapsiftup_max,
    _siftdown as heapsiftdown,
    _siftup as heapsiftup
)

def heappush_max(heap: list[_T], item: _T):
    '''Push item onto heap, maintaining the heap invariant.'''
    heap.append(item)
    heapsiftdown_max(heap, 0, len(heap)-1)

def heapreplace_max(heap: list[_T], item: _T) -> _T:
    '''Pop and return the current largest value, and add the new item.

    This is more efficient than heappop_max() followed by heappush_max(), and can be
    more appropriate when using a fixed-size heap.  Note that the value
    returned may be larger than item!  That constrains reasonable uses of
    this routine unless written as part of a conditional replacement:

        if item > heap[0]:
            item = heapreplace_max(heap, item)
    '''
    returnitem = heap[0]
    heap[0] = item
    heapsiftup_max(heap, 0)
    return returnitem

def heappushpop_max(heap: list[_T], item: _T) -> _T:
    '''Fast version of a heappush_max followed by a heappop_max.'''
    if heap and heap[0] > item:
        item, heap[0] = heap[0], item
        heapsiftup_max(heap, 0)
    return item

from typing import Generic

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 MaxHeap(HeapProtocol[_T], UserList[_T]):
    def __init__(self, iterable: Iterable[_T] = None):
        super().__init__(iterable)
        heapify_max(self.data)
    def pop(self): return heappop_max(self.data)
    def push(self, item: _T): heappush_max(self.data, item)
    def pushpop(self, item: _T): return heappushpop_max(self.data, item)
    def replace(self, item: _T): return heapreplace_max(self.data, item)
Back to top page