Python heapq 与 sorted 的复杂度和性能比较
我对Python还比较陌生（使用的是3.x版本的语法），想了解一下heapq和sorted在复杂度和性能方面的区别。
我已经实现了一个基于heapq的解决方案，用于一个贪心算法“寻找最佳工作安排”。但是后来我了解到可以使用'sorted'结合operator.itemgetter()和reverse=True。
可惜的是，我没有找到关于'sorted'和heapq的复杂度和性能预期的解释。
3 个回答
heapq 是用一种叫做 二叉堆 的结构来实现的。关于 二叉堆 和 heapq，有几个关键点需要注意：
- 它不支持搜索功能
- 插入数据的平均时间是固定的
- 删除数据的平均时间是 O(log n)
关于 二叉堆 的更多信息可以在这里找到： http://en.wikipedia.org/wiki/Binary_heap
虽然 heapq 是一种具有 二叉堆 特性的 数据结构，但使用 sorted 是一个不同的概念。sorted 返回的是一个 排序好的列表，这基本上是一个结果，而 heapq 是你在不断操作的 数据结构，可以选择通过 sorted 来进行排序。
关于 sorted 的更多信息可以在这里找到： https://docs.python.org/3.4/library/functions.html#sorted
你具体想要达成什么目标呢？
对提问者评论的回应：
你为什么觉得需要特别使用 heapq 呢？二叉堆 是一种专门的 数据结构，根据你的需求，很可能并不需要它。
你似乎对性能非常关注，但不太清楚原因。如果某个东西的性能不好，但它的总体时间并不重要，那在大局上其实没什么关系。在总体情况下，dict 或 list 的表现通常都很好。你为什么特别觉得需要 heapq 呢？
我在想这是不是一种 不要让完美成为好的敌人 的情况。
使用 C 扩展 来编写 Python 是一种 小众 的用法，通常只在性能确实是个大问题的情况下使用。（比如，如果你处理的是大文件，而性能是你的主要关注点，那么使用一个 C 扩展 的 XML 解析器可能比纯 Python 的要好。）
关于在复杂的结构情况下：用 sorted 排序并通过 .append() 添加元素是否更快：
我仍然不太清楚这里的使用场景是什么。正如我上面提到的，sorted 和 heapq 实际上是两个不同的概念。
你为什么对性能如此关注？（如果没有其他尚未说明的因素，我觉得你可能过于强调了代码中最佳性能的重要性。）
heapq模块里的nlargest()和nsmallest()这两个函数特别适合用来找比较少的几个项目。如果你只是想找一个最小值或最大值，使用min()和max()会更合适，因为它们速度更快，直接用sorted排序后再切片就可以了。如果你想找N个最小或最大值，而这个N相对于整个数据量来说比较小，这两个函数的表现会更好。虽然在代码中不一定非得用到heapq，但这是个有趣的话题，值得去了解一下。
如果你使用二叉堆来按顺序弹出所有元素，实际上你就是在做一种叫做堆排序的操作。这个方法比起sorted函数中的排序算法要慢，除了它的实现是纯Python之外。
如果你需要动态添加元素，也就是说添加和插入的顺序不确定，那么heapq会比sorted快。在任何堆中添加新元素并保持内部顺序，比在每次插入后重新排序整个数组要快得多。
如果你之后需要按顺序取出所有元素，那么sorted会更快。
它们唯一能竞争的地方是，当你需要从集合中提取一些最小（或最大）元素时。虽然有专门的算法来处理这种情况，但到底是heapq快还是sorted快，取决于初始数组的大小和你需要提取的元素数量。