사용자 도구

사이트 도구


ps:teflib:priorityqueue

priorityqueue.py

imports and globals

import heapq
from collections.abc import Iterable
from typing import TypeVar

_T = TypeVar('_T')

UpdatableHeap

코드

# N UpdatableHeap
# I {"version": "1.1", "import": ["heapq"], "abc": ["Iterable"], "typing": ["TypeVar"], "const": ["_T"]}
_hpop, _hpush = heapq.heappop, heapq.heappush


class UpdatableHeap():
    """ Min-heap that supports delete and update operations."""

    __slots__ = ('_heap', '_del_heap')

    def __init__(self, values: Iterable[_T] = ()):
        self._heap = list(values)
        heapq.heapify(self._heap)
        self._del_heap = []

    def __len__(self):
        return len(self._heap) - len(self._del_heap)

    def push(self, val: _T):
        _hpush(self._heap, val)

    def pop(self) -> _T:
        p = _hpop(self._heap)
        while self._del_heap and self._del_heap[0] == self._heap[0]:
            _hpop(self._del_heap)
            _hpop(self._heap)
        return p

    def top(self) -> _T:
        return self._heap[0]

    def delete(self, val: _T):
        _hpush(self._del_heap, val)
        while self._del_heap and self._del_heap[0] == self._heap[0]:
            _hpop(self._del_heap)
            _hpop(self._heap)

    def update(self, val: _T, new_val: _T):
        _hpush(self._del_heap, val)
        _hpush(self._heap, new_val)

설명

이 코드를 사용하는 문제

출처문제 번호Page레벨
BOJ15459Haybale Feast골드 1
BOJ1572중앙값플래티넘 5
BOJ7662이중 우선순위 큐골드 5
BOJ9426중앙값 측정플래티넘 5
프로그래머스42628이중우선순위큐Level 3

토론

댓글을 입력하세요:
M W H Q X
 
ps/teflib/priorityqueue.txt · 마지막으로 수정됨: 2022/06/29 02:35 저자 teferi