Welcome, guest | Sign In | My Account | Store | Cart

Priority queues are a kind of container that allows specification of the relative order of the data.

Python, 25 lines
 1
 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, I’ve 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.

1 comment

Grant Jenks 9 years, 6 months ago  # | flag

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.