我是 python 的新手(使用 v3.x 语法)，希望得到有关 heapq 与排序的复杂性和性能的说明。
我已经为贪婪的“找到最佳工作安排”算法实现了基于 heapq 的解决方案。但后来我了解了将“排序”与 operator.itemgetter() 和 reverse=True 一起使用的可能性。
遗憾的是，我找不到任何关于“已排序”与 heapq 的预期复杂性和/或性能的解释。
最佳答案
如果你使用二叉堆按顺序弹出所有元素，你做的事情基本上是heapsort .它比 sorted function 中的排序算法慢除了它的实现是纯 python。
heapq 比 sorted 更快，以防您需要动态添加元素，即添加和插入可能以未指定的顺序进行。在任何堆中添加保留内部顺序的新元素都比在每次插入后重新排序数组更快。
如果稍后需要按顺序检索所有元素，sorted 会更快。
他们可以竞争的唯一问题 - 如果您需要集合中最小(或最大)元素的一部分。虽然there are special algorigthms for that case ，heapq 还是 sorted 会更快取决于初始数组的大小和您需要提取的部分。
关于Python heapq 与排序的复杂性和性能，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24666602/