实现优先级队列 --heapq模块

# coding=utf-8
# example.py
#
# Example of a priority queue

import heapq

class PriorityQueue:
    def __init__(self):
        self._queue = []
        self._index = 0

    def push(self, item, priority):
        heapq.heappush(self._queue, (-priority, self._index, item)) #在这里就是依据优先级的负数作排序依据，最小的在左边，是第0个值
        self._index += 1    #当优先级一样是，index按照小的先输出，保证了先进先出

    def pop(self):
        return heapq.heappop(self._queue)[-1]   #返回item

# Example use
class Item:
    def __init__(self, name):
        self.name = name
    def __repr__(self):
        return ‘Item({!r})‘.format(self.name)#！后面可以加s r分别对应str() repr() ,和%用法类似，s没括号，r有括号

q = PriorityQueue()
q.push(Item(‘foo‘), 1)
q.push(Item(‘bar‘), 5)
q.push(Item(‘spam‘), 4)
q.push(Item(‘grok‘), 1)

print("Should be bar:", q.pop())
print("Should be spam:", q.pop())
print("Should be foo:", q.pop())
print("Should be grok:", q.pop())

a=[5,8,9]
b=[5,1,2]
c=[4,6,7]
ss=[]
heapq.heappush(ss,a)#是按照a中序列的第一个作排序依据的
heapq.heappush(ss,b)
heapq.heappush(ss,c)
print ss
s=heapq.heappop(ss)[-1]
print s,ss
s=heapq.heappop(ss)[-1]
print s,ss
s=heapq.heappop(ss)[-1]
print s,ss