Python进阶编程：编写更高效、优雅的Python代码
上QQ阅读APP看书，第一时间看更新
上一章目录下一章

3.5　实现一个优先级队列

在实际应用中，为了更便利地操作队列，我们需要将队列按优先级排序，并在队列上的每次pop()操作后返回优先级最高的元素。

下面使用heapq模块实现一个简单的优先级队列，相关代码（priority_queue.py）如下：

# 优先级队列
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))
        self._index += 1

    def pop(self):
        return heapq.heappop(self._queue)[-1]

优先级队列的使用方式如下（priority_queue.py）：

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

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

if __name__ == "__main__":
    priority_queue = PriorityQueue()
    priority_queue.push(Item('queue_1'), 1)
    priority_queue.push(Item('queue_2'), 3)
    priority_queue.push(Item('queue_3'), 5)
    priority_queue.push(Item('queue_4'), 3)

    print(priority_queue.__dict__.get('_queue')[0])
    print(f'pop item is:{priority_queue.pop()}')

    print(priority_queue.__dict__.get('_queue')[0])
    print(f'pop item is:{priority_queue.pop()}')

    print(priority_queue.__dict__.get('_queue')[0])
    print(f'pop item is:{priority_queue.pop()}')

    print(priority_queue.__dict__.get('_queue')[0])
    print(f'pop item is:{priority_queue.pop()}')

    print(priority_queue.__dict__)

执行py文件，输出结果如下：

(-5, 2, Item('queue_3'))
pop item is:Item('queue_3')
(-3, 1, Item('queue_2'))
pop item is:Item('queue_2')
(-3, 3, Item('queue_4'))
pop item is:Item('queue_4')
(-1, 0, Item('queue_1'))
pop item is:Item('queue_1')
{'_queue': [], '_index': 4}

由执行结果可知，第一个pop()操作返回了优先级最高的元素。

注意　如果两个有着相同优先级的元素（queue_2和queue_4），pop()操作是按照它们被插入到队列的顺序返回的——先插入的元素先返回。

heapq.heappush()和heapq.heappop()函数分别用于在队列_queue上插入和删除第一个元素。队列_queue保证第一个元素拥有最高优先级。

heappop()函数总是返回最小的的元素，这是保证队列pop()操作返回正确元素的关键。另外，由于push()和pop()操作时间复杂度为O(logN)，其中N是堆的大小，因此即使N很大，执行操作的运行速度也很快。

在上面示例代码中，队列包含一个（-priority,index,item）的元组。设置优先级为负数的目的是使元素按照优先级从高到低排序。这与普通的按优先级从低到高排序的堆排序恰巧相反。

index变量的作用是保证同等优先级元素的正确排序。通过保存一个不断增加的index下标变量，可确保元素按照它们插入的顺序排序。index变量在相同优先级元素比较的情况下起到重要作用。

下面通过示例进一步讲解优先级队列，相关代码（priority_queue_1.py）如下：

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

if __name__ == "__main__":
    queue_1 = Item('queue_1')
    queue_2 = Item('queue_2')
    print(queue_1 < queue_2)

执行py文件，输出结果如下：

Traceback (most recent call last):
  File "/Users/lyz/Desktop/python-workspace/advanced_programming/chapter1/priority_queue_1.py", line 8, in <module>
    print(queue_1 < queue_2)
TypeError: '<' not supported between instances of 'Item' and 'Item'

如果你使用元组（priority,item），只要两个元素的优先级不同就能比较。但当两个元素优先级一样时，比较操作就会出错，这时我们可以在代码priority_queue_1.py中做修改：

queue_1 = (1, Item('queue_1'))
queue_2 = (3, Item('queue_2'))
queue_3 = (1, Item('queue_3'))
print(queue_1 < queue_2)
print(queue_1 < queue_3)

输出结果如下：

True
Traceback (most recent call last):
  File "/Users/lyz/Desktop/python-workspace/advanced_programming/chapter1/priority_queue_1.py", line 14, in <module>
    print(queue_1 < queue_3)
TypeError: '<' not supported between instances of 'Item' and 'Item'

由此可见，通过引入另外的index变量组成三元组（priority,index,item），能很好地避免上面示例中的错误，因为不可能有两个元素有相同的index值。

Python在做元组比较时，如果前面的比较已经可以确定结果，后面的比较操作就不会发生了。我们可以继续在priority_queue_1.py中添加如下修改：

queue_1 = (1, 0, Item('queue_1'))
queue_2 = (3, 1, Item('queue_2'))
queue_3 = (1, 2, Item('queue_3'))
print(queue_1 < queue_2)
print(queue_1 < queue_3)

执行py代码，输出结果如下：

True
True

如果想在多个线程中使用同一个队列，那么需要增加适当的锁和信号量机制。

有想深入了解heapq模块的读者可以仔细研读heapq模块的官方文档。

上一章目录下一章