最近刷题，碰到好几个问题都需要使用优先队列解决。

谈优先队列之前，先了解下什么是队列。队列拥有FIFO的特点，也就是先进先出，比如现实生活中的排队现象，当然现实生活中的排队现象更复杂一些，除了先进先出，还有插队、中途离队等情况。
维基百科的定义如下：

队列，又称为伫列（queue），计算机科学中的一种抽象资料类型，是先进先出（FIFO, First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为rear）进行插入操作，在前端（称为front）进行删除操作。
队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。

什么是优先队列？维基百科的定义如下：

优先队列（priority queue）是计算机科学中的一类抽象数据类型。优先队列中的每个元素都有各自的优先级，优先级最高的元素最先得到服务；优先级相同的元素按照其在优先队列中的顺序得到服务。优先队列通常使用“堆”（heap）实现。
Python的heapq 模块实现了在链表基础上的二叉最小堆，queue 模块将heapq模块包装实现了PriorityQueue类。

优先队列，和队列相比，不是按照FIFO出队的，而是按照优先级，比如航班的vip客户和普通客户在订购退票时vip客户优先级更高。

堆，是一种特殊的优先队列，最小的优先级最高，最先出队。

我来演示下Python如何将一个列表转换为堆、添加新的元素、获取最小的元素

In [1]: nums = [3, 1, 5, 2, 8]

In [2]: import heapq

In [3]: heapq.heapify(nums)

In [4]: nums
Out[4]: [1, 2, 5, 3, 8]

In [6]: heapq.heappush(nums, 0)

In [7]: nums
Out[7]: [0, 2, 1, 3, 8, 5]

In [9]: heapq.heappop(nums)
Out[9]: 0

In [10]: nums
Out[10]: [1, 2, 5, 3, 8]

Python没有实现大顶堆，也就是最大的值在队列的第一个，我在网上看到有网友的一个取巧方法，就是在前面加负号，这样最大值就变成最小值了，只是取出来的时候需要再转换一下，演示如下：

In [17]: max_heap = [-3, -1, -4, -8]

In [18]: heapq.heapify(max_heap)

In [19]: max_heap
Out[19]: [-8, -3, -4, -1]

In [20]: heapq.heappush(max_heap, -10)

In [21]: max_heap
Out[21]: [-10, -8, -4, -1, -3]

获取堆中最大或最小的n个值，演示如下：

In [23]: heapq.nlargest(1, max_heap)
Out[23]: [-1]

In [24]: heapq.nlargest(2, max_heap)
Out[24]: [-1, -3]

In [25]: heapq.nsmallest(1, max_heap)
Out[25]: [-10]

In [26]: heapq.nsmallest(2, max_heap)
Out[26]: [-10, -8]

从《数据结构与算法Python语言实现》，机械工业出版社，ISBN 978-7-111-60660-4摘录关于堆的一些描述：

堆是一颗二叉树，满足两个附加的属性，关系属性和结构属性。
关系属性，Heap-Order属性，在堆T中，对于除了根的每个位置p，存储在p中的键值大于或等于存储在p的父节点的键值。
作为Heap-Order属性的结果，T中从根到叶子节点的路径上的键值是以非递减顺序排列的。也就是说，一个最小的键总是存储在T的根节点上。
由于效率的缘故，我门想让堆T的高度尽可能小。我们通过坚持让堆T满足结构属性中的附加属性，来强制满足让堆堆高度尽可能小这一需求，它必须是完全二叉树。完全二叉树属性： 一个高度为h的堆T是一颗完全二叉树，那么T的0，1，2，……，h-1层上有可能达到节点数的最大值（即，i层上有2的i次方个节点，且0 <= i <= h-1），并且剩余的节点在h级尽可能保存在最左的位置。

在堆中增加新的节点，为了满足完全二叉树的属性，需要添加到最下层最左边元素的右邻，如果最下层满了，需要添加到新的一层的最左边。然后，向上冒泡实现顺序的调整。
移除最小元素，不是直接删除，这样会把一棵树变成两颗无法联通的树。采取了一个巧妙的方法，将树的最下层最右边的节点删除，将它的值复制到根节点，然后向下冒泡，调整顺序。调整顺序的过程中，也有技巧，在需要交换时，和左右孩子中小的交换，可以减少该元素成为另外一个节点的父节点时的调整成本。