Python 3 combined priority queue + dict. pop the smallest (key, value) pair by value comparison order or access any value by key. assigning to a key which is still in the queue will mark the old value dead and push the new one.

pqd.py

import heapq

class PQDItem:
    def __init__(self, k, v):
        self.v = v
        self.k = k
        self.dead = False
    def __lt__(self, other):
        return self.v < other.v

class PQD:
    def __init__(self, d):
        self.d = {k: PQDItem(k,v) for k,v in d.items()}
        self.q = list(self.d.values())
        heapq.heapify(self.q)
        
    def pop(self):
        item = None
        while item is None or item.dead:
            item = heapq.heappop(self.q)
        del self.d[item.k]
        return item.k, item.v
    
    def __getitem__(self, k):
        return self.d[k].v
    
    def __setitem__(self, k, v):
        if k in self.d:
            self.d[k].dead = True
        item = PQDItem(k, v)
        self.d[k] = item
        heapq.heappush(self.q, item)
    
    def __contains__(self, k):
        return k in self.d
    
    def __len__(self):
        return len(self.d)