Creating a python priority queue

Question

I would like to create a priority queue in python in which the queue contains various dictionaries with their priority numbers. Therefore, when the "get function" function is called, the dictionary with the highest priority (lowest number) will be removed from the queue and when the "add function" function is called, the new dictionary will be added to the queue and sorted based on its priority number.

Please, help...

Thanks in advance!

Answer 1

Use the heapq module in the standard library.

You do not indicate how you wanted to associate priorities with dictionaries, but here is a simple implementation:

import heapq class MyPriQueue(object): def __init__(self): self.heap = [] def add(self, d, pri): heapq.heappush(self.heap, (pri, d)) def get(self): pri, d = heapq.heappop(self.heap) return d 

Answer 2

This is what I usually present as a side note in some of my template conversations:

 class PriorityQueue(object): def __init__(self, key=lambda x: x): self.l = [] self.key = key def __len__(self): return len(self.l) def push(self, obj): heapq.heappush(self.l, (self.key(obj), obj)) def pop(self): return heapq.heappop(self.l)[-1] 

Obviously, OP requirements should use operator.itemgetter('priority') as the key argument when creating the PriorityQueue instance (of course, import operator is required at the top of the module ;-).

Answer 3

You can do this by adding a dict object to the class and search inside it.