cp-library

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

View the Project on GitHub kobejean/cp-library

:warning: cp_library/ds/heap/max_priority_queue_cls.py

Depends on

Code

import cp_library.__header__
from cp_library.bit.pack.packer_cls import Packer
import cp_library.ds.__header__
import cp_library.ds.heap.__header__
from cp_library.ds.heap.fast_heapq import heapify_max, heappop_max, heappush_max, heappushpop_max, heapreplace_max
from cp_library.ds.heap.heap_proto import HeapProtocol

class MaxPriorityQueue(HeapProtocol[int]):
    def __init__(que, N: int, ids: list[int] = None, priorities: list[int] = None, /):
        que.pkr = Packer(N)
        if ids is None: que.data = elist(N)
        elif priorities is None: heapify_max(ids); que.data = ids
        else:
            que.data = [0]*(M := len(ids))
            for i in range(M): que.data[i] = que.pkr.enc(priorities[i], ids[i])
            heapify_max(que.data)
    def pop(que): return que.pkr.dec(heappop_max(que.data))
    def push(que, priority: int, id: int): heappush_max(que.data, que.pkr.enc(priority, id))
    def pushpop(que, priority: int, id: int): return que.pkr.dec(heappushpop_max(que.data, que.pkr.enc(priority, id)))
    def replace(que, priority: int, id: int): return que.pkr.dec(heapreplace_max(que.data, que.pkr.enc(priority, id)))
    def peek(que): return que.pkr.dec(que.data[0])
from cp_library.ds.elist_fn import elist
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''



class Packer:
    def __init__(P, mx: int):
        P.s = mx.bit_length()
        P.m = (1 << P.s) - 1
    def enc(P, a: int, b: int): return a << P.s | b
    def dec(P, x: int) -> tuple[int, int]: return x >> P.s, x & P.m
    def enumerate(P, A, reverse=False): P.ienumerate(A:=A.copy(), reverse); return A
    def ienumerate(P, A, reverse=False):
        if reverse:
            for i,a in enumerate(A): A[i] = P.enc(-a, i)
        else:
            for i,a in enumerate(A): A[i] = P.enc(a, i)
    def indices(P, A: list[int]): P.iindices(A:=A.copy()); return A
    def iindices(P, A):
        for i,a in enumerate(A): A[i] = P.m&a



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
from typing import TypeVar
_T = TypeVar('T')
_U = TypeVar('U')

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 MaxPriorityQueue(HeapProtocol[int]):
    def __init__(que, N: int, ids: list[int] = None, priorities: list[int] = None, /):
        que.pkr = Packer(N)
        if ids is None: que.data = elist(N)
        elif priorities is None: heapify_max(ids); que.data = ids
        else:
            que.data = [0]*(M := len(ids))
            for i in range(M): que.data[i] = que.pkr.enc(priorities[i], ids[i])
            heapify_max(que.data)
    def pop(que): return que.pkr.dec(heappop_max(que.data))
    def push(que, priority: int, id: int): heappush_max(que.data, que.pkr.enc(priority, id))
    def pushpop(que, priority: int, id: int): return que.pkr.dec(heappushpop_max(que.data, que.pkr.enc(priority, id)))
    def replace(que, priority: int, id: int): return que.pkr.dec(heapreplace_max(que.data, que.pkr.enc(priority, id)))
    def peek(que): return que.pkr.dec(que.data[0])

def elist(est_len: int) -> list: ...
try:
    from __pypy__ import newlist_hint
except:
    def newlist_hint(hint):
        return []
elist = newlist_hint
Back to top page