Priority queues are a kind of container that allows specification of the relative order of the data.
Python, 25 lines
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | import bisect
class PriorityQueue:
def __init__(self):
self.queue = []
def append(self,data,priority):
"""append a new element to the queue according to its priority"""
bisect.insort(self.queue,(priority,data))
def pop(self,n):
"""pop the hightest element of the queue. The n argument is
here to follow the standard queue protocol """
return self.queue.pop(0)[1]
#sample
a=PriorityQueue()
a.append('L',5)
a.append('E',4)
a.append('L',5)
a.append('O',8)
a.append('H',1)
for i in range(5):
print a.pop(0),
print
|
This kind of container is generally implemented with B-Trees. Since Python does not support this kind of structure in standard, Ive used an ordered list instead. If you have a great need for performances, you should have a look at the Vault. It contains several C extensions that define B-Trees.
Tags: algorithms
If you're looking for an API similar to that provided by this priority queue, check out the sortedcontainers module. It implements sorted list, sorted dict, and sorted set data types in pure-Python and is fast-as-C implementations (even faster!). Learn more about sortedcontainers, available on PyPI and github.