堆(Heap)

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

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

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

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

优先级队列(Priority Queue)
优先级队列的特点:

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

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

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