首页 > 代码库 > 实现优先级队列 --heapq模块

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

 以给定的优先级对元素进行排序,每次pop删除优先级最高的

# 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

 结果:

 

技术分享
H:\Python27_64\python.exe H:/myfile/python-cookbook-master/src/1/implementing_a_priority_queue/example.py
(Should be bar:, Item(bar))
(Should be spam:, Item(spam))
(Should be foo:, Item(foo))
(Should be grok:, Item(grok))
[[4, 6, 7], [5, 8, 9], [5, 1, 2]]
7 [[5, 1, 2], [5, 8, 9]]
2 [[5, 8, 9]]
9 []

进程已结束,退出代码0
View Code

 

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