Skip to content

Instantly share code, notes, and snippets.

@victor-shepardson
Last active January 20, 2020 05:01
Show Gist options
  • Save victor-shepardson/d439ca95f5e4d26385217b55f95e30a1 to your computer and use it in GitHub Desktop.
Save victor-shepardson/d439ca95f5e4d26385217b55f95e30a1 to your computer and use it in GitHub Desktop.
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.
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment