Python priority queue (with priority updating) built on top of heapq

priority_queue.py

from heapq import heappush, heappop
import itertools

__all__ = ["PriorityQueue"]


class PriorityQueue:
    sentinel = object()

    def __init__(self):
        self.heap, self.entries = [], {}
        self.counter = itertools.count()

    def push(self, item, priority):
        if item in self.entries:
            self.entries[item][2] = self.sentinel

        entry = self.entries[item] = [priority, next(self.counter), item]
        heappush(self.heap, entry)

    def pop(self):
        while True:
            priority, count, item = heappop(self.heap)

            if item is not self.sentinel:
                del self.entries[item]
                return item