优先队列：PriorityQueue

Python使用优先队列代码：

import Queue
q = Queue.PriorityQueue()
q.put(1) #添加元素
q.get()  #删除元素

python的优先队列基于最小堆实现。

Heap（堆）是一个除了底层节点外的完全填满的二叉树，底层可以不完全，左到右填充节点。而最小堆意味着，任一非终端节点的数据值均不大于其左子节点和右子节点的值。如图：

python优先队列插入和删除的时间复杂度均为logn，get()方法默认返回值最小元素。

使用heapq自己实现PriorityQueue:

from heapq import heappush, heappop
class PriorityQueue:
    def __init__(self):
        self._queue = []

    def put(self, item, priority):
        heappush(self._queue, (priority, item))

    def get(self):
        return heappop(self._queue)

q = PriorityQueue()
q.put('world', 2)
q.put('hello', 1)
>>>q.get()[1]
hello
>>>q.get()[1]
world

修改一下使得get()返回值最大的元素：

from heapq import heappush, heappop
class PriorityQueue:
    def __init__(self):
        self._queue = []

    def put(self, item, priority):
        heappush(self._queue, (-priority, item))

    def get(self):
        return heappop(self._queue)

q = PriorityQueue()
q.put('world', 2)
q.put('hello', 1)
>>>q.get()[1]
world
>>>q.get()[1]
hello