用Python实现一个优先级队列(Priority Queue)

堆(Heap)

在实现一个优先队列之前,先简单介绍 heap(堆)的概念。堆,是对于每一个父节点上的值都小于或等于子节点的值的二叉树。此外,一个堆必须是一个完整的二叉树,除了最底层其他每一级必须是被完整填充的。因此,堆的最重要的一个特点就是:首项heap[0]总是最小的一项

而堆化(heapify)则是将一个二叉树转化为一个堆数据结构的过程。在Python中,我们可以用自带heapq模块中的heapify(x)函数来实现将一个列表 x 转化为一个堆。时间复杂度为线性O(N). 代码如下:

>>> import heapq
>>> x = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
>>> heap = list(x)
>>> heapq.heapify(heap)
>>> heap
[-4, 2, 1, 23, 7, 2, 18, 23, 42, 37, 8]

heap 是被"堆化"后的列表,heap[0] = -4为最小项。注意:此时heap 的数据类型仍是一个list

另外,可以用heappop(), heappush()heapreplace()等方法来对一个堆列表进行操作。例如,heappop()会从堆列表中拿出并返回最小项,并且使堆保持不变(即heap[0]仍为最小项)。

>>> heapq.heappop(heap)
-4
>>> heapq.heappop(heap)
1
>>> heapq.heappop(heap)
2
>>> heap
[2, 7, 8, 23, 42, 37, 18, 23]

优先级队列(Priority Queue)

优先级队列的特点:

  • 给定一个优先级(Priority)
  • 每次pop操作都会返回一个拥有最高优先级的项

代码如下:

import heapq

class PriorityQueue(object):
    def __init__(self):
        self._queue = []        #创建一个空列表用于存放队列
        self._index = 0        #指针用于记录push的次序
    
    def push(self, item, priority):
        """队列由(priority, index, item)形式的元祖构成"""
        heapq.heappush(self._queue, (-priority, self._index, item)) 
        self._index += 1
        
    def pop(self):
        return heapq.heappop(self._queue)[-1]    #返回拥有最高优先级的项

class Item(object):
    def __init__(self, name):
        self.name = name

    def __repr__(self):
        return 'Item: {!r}'.format(self.name)

if __name__ == '__main__':
    q = PriorityQueue()
    q.push(Item('foo'), 5)
    q.push(Item('bar'), 1)
    q.push(Item('spam'), 3)
    q.push(Item('grok'), 1)
    for i in range(4):
        print(q._queue)
        print(q.pop())

对队列进行4次pop()操作,打印结果如下:

[(-5, 0, Item: 'foo'), (-1, 1, Item: 'bar'), (-3, 2, Item: 'spam'), (-1, 3, Item: 'grok')]
Item: 'foo'
[(-3, 2, Item: 'spam'), (-1, 1, Item: 'bar'), (-1, 3, Item: 'grok')]
Item: 'spam'
[(-1, 1, Item: 'bar'), (-1, 3, Item: 'grok')]
Item: 'bar'
[(-1, 3, Item: 'grok')]
Item: 'grok'

可以观察出pop()是如何返回一个拥有最高优先级的项。对于拥有相同优先级的项(bar和grok),会按照被插入队列的顺序来返回。代码的核心是利用heapq模块,之前已经说过,heapq.heappop()会返回最小值项,因此需要把 priority 的值变为负,才能让队列将每一项按从最高到最低优先级的顺序级来排序。

参考文献:

  1. Python 3.6 Documentation
  2. Python Cookbook (3rd), O'Reilly.

声明

原创文章,仅用于个人学习及参考,禁止转载。一切解释权归原作者所有。文中如有错误或不足之处请及时指出。

相关推荐