In python there is a class PriorityQueue. This class literally is what it says: you can add elements and take out the smallest. In particular, if you add an element twice, it sits in in the queue twice (so you get it twice).
~> python3 Python 3.4.3 (default, Jan 1 2016, 12:53:34) [GCC 4.2.1 20070831 patched [FreeBSD]] on freebsd9 Type "help", "copyright", "credits" or "license" for more information. >>> from queue import PriorityQueue >>> q = PriorityQueue() >>> q.put(4) >>> q.put(3) >>> q.put(4) >>> q.put(5) >>> q.qsize() 4 >>> q.get() 3 >>> q.get() 4 >>> q.get() 4 >>> q.get() 5 >>> quit() ~>
While such a data structure is useful in general, it can have fun effects when used (e.g., when someone demonstrates how Dijkstra's algorithm works) in a place where you actually need a different data structure, one with the operations adding an element with a priority, updating the priority to a smaller value, and removing value with the smallest priority. Using a PriorityQueue with priority-value pairs almost works (hint: tuples are ordered lexicographically) except that you find, that nodes are visited more often than you expect. Of course, it is not hard to write a wrapper around PriorityQueue that provides this semantics.
from queue import PriorityQueue
class PQueue():
"""Queue which contains elements with a priority
Supported operations are adding elements, updating
the priority to a smaller value, and removing the
element with the smallest priority.
"""
def __init__(self):
self.entries = {} # The actual entries
self.q = PriorityQueue() # A priority queue of the entries,
# might, however, contain elements
# not in the PQueue
def put(self, priokey):
"""Update the priority of an element, adding it if not yet present
Take an (priority, element) pair and update the priority of the element,
if the new value is smaller than the current value. If the element is
not present in the queue, add it.
"""
(prio, key) = priokey
if key in self.entries:
oldprio = self.entries[key]
if prio < oldprio:
self.entries[key] = prio
self.q.put(priokey)
else:
self.entries[key] = prio
self.q.put(priokey)
def qsize(self):
return (len(set(self.entries)))
def empty(self):
return self.qsize() == 0
def get(self):
"""Remove the element with the smallest priority form the queue
Return the pair of the priority and the element itself.
"""
assert(not self.empty())
while True:
(prio, key) = self.q.get()
if key in self.entries and self.entries[key] == prio:
del self.entries[key]
return (prio, key)