python映射和优先级队列的区别（用Python实现优先级队列的3种方法）
python映射和优先级队列的区别（用Python实现优先级队列的3种方法）不过标准库提供的bisect.insort方法让你能够在O(log n)的时间里找到需要插入的位置，这帮缓慢的插入操作改善了部分性能。使用排序列表你可以快速地获取或删除最大的或者最小的元素，缺点是向列表中插入元素是一个很慢的操作，复杂度在O(n)。我们以操作系统的任务调度为例：高优先级的任务（比如实时游戏）应该先于低优先级的任务（比如后台下载软件更新）执行。通过在优先级队列中依据任务的紧急程度排序，我们能让最紧急的任务优先得到执行。我们下面讲解几种实现优先级队列的方法，有的使用的是Python的内置数据结构，有的使用的是Python标准库提供的数据结构。两种情况各有千秋，在我的心中其中有一种方法在绝大多数时候都是最优的方案，当然你也需要自己去判断哪个才是你最需要的。手动维护排序列表
你能想出几种方法来在Python中实现优先级队列？阅读下面文章并找出Python标准库提供了哪些方案？
优先级队列是一种容器型数据结构，它能管理一队记录，并按照排序字段（例如一个数字类型的权重值）为其排序。由于是排序的，所以在优先级队列中你可以快速获取到最大的和最小的值。
你可以认为优先级队列是一种修改过的普通队列：普通队列依据记录插入的时间来获取下一个记录，优先级队列依据优先级来获取下一个记录，而优先级取决于排序字段的值。
优先级队列经常用来解决调度问题，比如给更紧急的任务更高的优先级。
我们以操作系统的任务调度为例：高优先级的任务（比如实时游戏）应该先于低优先级的任务（比如后台下载软件更新）执行。通过在优先级队列中依据任务的紧急程度排序，我们能让最紧急的任务优先得到执行。
我们下面讲解几种实现优先级队列的方法，有的使用的是Python的内置数据结构，有的使用的是Python标准库提供的数据结构。两种情况各有千秋，在我的心中其中有一种方法在绝大多数时候都是最优的方案，当然你也需要自己去判断哪个才是你最需要的。
手动维护排序列表
使用排序列表你可以快速地获取或删除最大的或者最小的元素，缺点是向列表中插入元素是一个很慢的操作，复杂度在O(n)。
不过标准库提供的bisect.insort方法让你能够在O(log n)的时间里找到需要插入的位置，这帮缓慢的插入操作改善了部分性能。
如果是把元素放到队列的最后，然后直接重新排序，那么复杂度是O(nlog n)。
所以排序列表的这种实现方法，只有在插入操作很少的时候才合适。
heapq模块
heapq是一个二叉堆的实现，它内部使用内置的list对象，它无论插入还是获取最小元素复杂度都在O(log n)。
这个模块是实现优先级队列的一个很好的选择。
由于heapq只是提供了一个最小的堆实现，所以为了让它成为实用的优先级队列，还需要添加很多额外的代码来保证顺序，和提供其他必不可少的功能。
queue.PriorityQueue类
这个优先级队列内部使用了heapq，所以它的时间复杂度和heapq是相同的。
不同的是PriorityQueue的操作是同步的，提供锁操作，支持并发的生产者和消费者。
依据使用场景，它可能很有用，也可能有点太大了。通常来说它的基于类接口要比heapq的基于函数的接口更友好。
一个比较好的默认选项
在你的程序中应该使用哪一个优先级队列的实现呢？上面三种实现都有自己的使用场景，但是在我心里queue.PriorityQueue是最好的选择。
确实有时候它显得有点过重了，但是我很看重它的面向对象的接口，以及一个清晰地表意的名字。
译者：诗书塞外
英文原文：https://dbader.org/blog/priority-queues-in-python#.
