相信对于伫列的概念大家都不会陌生，这种先入先出的资料结构应用很广泛，像一般的生产消费都会用到伫列，关于Queue的用法介绍可以参考我之前的文章 python中的Queue与多程序（multiprocessing）还有栈，栈是一种先入后出的资料结构,优先伫列有别于普通的伫列与栈，在实现上，它一般通过堆这一资料结构，而堆其实是一种完全二叉树，它会对进入容器的元素进行排序（根据事先指定的规则），出队的顺序则会是二叉树的根结点代表的元素。接下来介绍几种优先伫列的实现。
通过heapq模组
heapq是一个二叉堆的实现，它内部使用内建的list物件，它无论插入还是获取最小元素复杂度都在O(log n)。这里主要用到它的heappush与heappop方法，heappush 方法需要传入两个引数，一个是列表(list)，另外是一个物件，这里的物件须是可比较物件，就是它可以通过cmp方法来比较大小，以下是在 python2 中的程式码实现
执行结果如下
(10, 'aaa')
(20, 'ddd')
(30, 'ccc')
(40, 'bbb')
可以看到，我放入 tasks 列表里的元素是个 set 物件，物件第一个元素是个 int 型别的数字，如果使用cmp方法进行比较的话
>>> cmp(10,20)
2-1
>>> cmp(10,10)
40
>>> cmp(10,5)
61
对于小于，等于，大于分别返回的是-1，0，1，其实这也是在定义sorted的实现方法,
可以看到在sorted方法里，它的排序算法是通过比较第一个元素的大小，小的排在前面，第一个元素相同再比较第二个元素，看返回之前的程式码，heapq.heappush 将 set 元素新增到列表元素以后，将对其进行重新排序，将最小的放在前面，于是就得到了上面的打印结果。
上面是使用python自带的 set 资料结构，可否自定义一种型别呢，比较在实现生活中，在上班的第一件事是给自已写一下今天要完成哪些事情，其实哪些事情的优先级比较高就是先做哪些事情，其实在上面也说到 sorted 方法，这个方法其实就是在呼叫物件的 __cmp__ 方法，好么我可以单独定义一个带有 __cmp__ 方法的物件则可以实现优先伫列中的物件排序。
执行结果：
上面的compareAble 类初始化有两个引数，一个是优先级，一个是事情的名字，我这里定义的是优先级数值越小排序越靠前，也可以定义成数值越大越靠前。如果优先级相同，则按照插入顺序来排序。
通过Queue,PriorityQueue型别实现
这个优先级伫列内部使用了heapq,不同的是PriorityQueue的操作是同步的，提供锁操作，支援并发的生产者和消费者，而且它的界面更加友好，它继承自Queue，所以好多Queue的方法可以直接使用
接下来通过一个生产消费的例项来说明优先伫列的使用
有三个生产者和二个消费者，生产者向伫列中生产有优先级的任务，消费者也是优先消费高级别的任务
执行结果：
可以看出，每次取出来的都是当前伫列中 priority 最小的数
python3 中的使用方法
上面的程式码无法在python3中执行，主要是因为python3没有cmp方法，执行得到的异常资讯是1TypeError: unorderable types: CompareAble() 需要在上面定义一个 __lt__ 方法
上面的程式码我修改了一点对于大小的判断，与之前的是反的，这里 priority 越大则越先返回，上面的程式码在 python2 中也可以执行，所有如果为了相容性可以选择定义使用 __lt__ 方法。
由于今日头条上发的文章对于程式码排版不太方便，所以我将程式码片段都使用了截图的方式，想要复制程式码请点选 "了解更多"来检视原文或者微信搜寻公众号"序语程言"
