5.1 优先队列的3种实现方式

考虑到我们希望有一个基于顾客忠诚度排序的优先顾客队列，忠诚度分数越高，优先级越高。在Python中实现优先队列，有多种方法，这里介绍其中常用的三种。

1.使用列表实现优先队列

一种非常简单明了的方法是使用普通列表，但每次添加元素时都需要对其进行排序。举例如下。

运行结果：

将元素添加到列表时，时间复杂度为 O （ n log n ）。因此，只有插入元素很少时才使用上述方法。

2.使用heapq实现优先队列

在Python中还可以使用heapq来实现优先队列，此方法的时间复杂度是 O （log n ），可用于最小元素的插入和提取。请注意，heapq仅具有最小堆实现。

运行结果：

3.使用queue.PriorityQueue实现优先队列

PriorityQueue在内部使用与5.1.2中相同的heapq实现，因此具有相同的时间复杂度。但是，它在两个关键方面有所不同。首先，它是同步的，因此它支持并发进程。其次，它是一个类接口，而不是heapq的基于函数的接口。因此，PriorityQueue在实现和使用Priority Queues时是经典OOP（面向对象）风格。

让我们为电影迷们建立一个优先队列。

运行结果： 1vzWGLLzv7hduHCGouQs331nPcGuYNSmkE5LHy2JhBLb9d9rdiTRqYGZi8ue2edb