python的优先权队列

python的优先权队列，根据优先权来进行队列排序，但是注意优先权队列使用heap实现，而heap不是稳定的排序，所以，想要实现同优先权内部也有序，则需要增加一个计数，表示该优先权的顺序。参考以下代码：

#!/usr/bin/python
from Queue import Queue
from Queue import PriorityQueue
a1='a1'
a2='a2'
a3='a3'
a4='a4'
a5='a5'

b1='b1'
b2='b2'
b3='b3'
b4='b4'
b5='b5'

q = Queue()
pq = PriorityQueue()
for i in xrange(5):
    p = 5 - i
    q.put("a"+str(p))
    q.put("b"+str(p))

    pq.put((p,"a"+str(p)))
    pq.put((p,"b"+str(p)))

for i in xrange(5):
    p = 5 - i
    q.put("a"+str(p)+str(i+5))
    q.put("b"+str(p)+str(i+5))

    pq.put((p,"a"+str(p)+str(i+5)))
    pq.put((p,"b"+str(p)+str(i+5)))

size = q.qsize()
print "queue item size:%s" %size
print "queue items:"
for i in xrange(size):
    print q.get()

size = pq.qsize()
print "priority queue item size:%s" %size
print "priority queue items:"
for i in xrange(size):
    print pq.get()

#"but priority queue with same priority is not queue, if we want so, do the following:"
import itertools
count = itertools.count()
poq = PriorityQueue()
for i in xrange(5):
    p = 5 - i
    poq.put((p,count.next(),"a"+str(p)))
    poq.put((p,count.next(),"b"+str(p)))

for i in xrange(5):
    p = 5 - i
    poq.put((p,count.next(),"a"+str(p)+str(i+5)))
    poq.put((p,count.next(),"b"+str(p)+str(i+5)))


size = poq.qsize()
print "priority ordered queue item size:%s" %size
print "priority ordered queue items:"
for i in xrange(size):
    print poq.get()

输入类似如下:

queue item size:20
queue items:
a5
b5
a4
b4
a3
b3
a2
b2
a1
b1
a55
b55
a46
b46
a37
b37
a28
b28
a19
b19
priority queue item size:20
priority queue items:
(1, 'a1')
(1, 'a19')
(1, 'b1')
(1, 'b19')
(2, 'a2')
(2, 'a28')
(2, 'b2')
(2, 'b28')
(3, 'a3')
(3, 'a37')
(3, 'b3')
(3, 'b37')
(4, 'a4')
(4, 'a46')
(4, 'b4')
(4, 'b46')
(5, 'a5')
(5, 'a55')
(5, 'b5')
(5, 'b55')
priority ordered queue item size:20
priority ordered queue items:
(1, 8, 'a1')
(1, 9, 'b1')
(1, 18, 'a19')
(1, 19, 'b19')
(2, 6, 'a2')
(2, 7, 'b2')
(2, 16, 'a28')
(2, 17, 'b28')
(3, 4, 'a3')
(3, 5, 'b3')
(3, 14, 'a37')
(3, 15, 'b37')
(4, 2, 'a4')
(4, 3, 'b4')
(4, 12, 'a46')
(4, 13, 'b46')
(5, 0, 'a5')
(5, 1, 'b5')
(5, 10, 'a55')
(5, 11, 'b55')

更详细资料，参考： http://hg.python.org/cpython/file/2.7/Lib/Queue.py http://docs.python.org/library/heapq.html?highlight=heapq#heapq