How can I make a unique value priority queue in Python?
Python has Queue.PriorityQueue, but I cannot see a way to make each value in it unique as there is no method for checking if a value already exists (like find(name) or similar). Moreover, PriorityQueue needs the priority to remain within the value, so I could not even search for my value, as I would also have to know the priority. You would use (0.5, myvalue) as value in PriorityQueue and then it would be sorted by the first element of the tuple.
The collections.deque class on the other hand does offer a function for checking if a value already exists and is even more natural in usage (without locking, but still atomic), but it does not offer a way to sort by priority.
There are some other implementations on stackoverflow with heapq, but heapq also uses priority within the value (e.g. at the first position of a tuple), so it seems not be great for comparison of already existing values.
Creating a python priority Queue
https://stackoverflow.com/questions/3306179/priority-queue-problem-in-python
What is the best way of creating a atomic priority queue (=can be used from multiple threads) with unique values?
Example what I’d like to add:
- Priority: 0.2, Value: value1
- Priority: 0.3, Value: value2
- Priority: 0.1, Value: value3 (shall be retrieved first automatically)
- Priority: 0.4, Value: value1 (shall not be added again, even though it has different priority)
Answer
You could combine a priority queue with a set:
import heapq
class PrioritySet(object):
def __init__(self):
self.heap = []
self.set = set()
def add(self, d, pri):
if not d in self.set:
heapq.heappush(self.heap, (pri, d))
self.set.add(d)
def get(self):
pri, d = heapq.heappop(self.heap)
self.set.remove(d)
return d
This uses the priority queue specified in one of your linked questions. I don't know if this is what you want, but it's rather easy to add a set to any kind of queue this way.