什么是Python的heapq模块？

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了什么是Python的heapq模块？，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2167字，纯文字阅读大概需要4分钟。

内容图文

我尝试了“heapq”并得出结论,我的期望与我在屏幕上看到的不同.我需要有人解释它是如何工作的以及它在哪里有用.

从第2.2节“排序”一书中的第Python Module of the Week页开始编写

If you need to maintain a sorted list as you add and remove values,
check out heapq. By using the functions in heapq to add or remove
items from a list, you can maintain the sort order of the list with
low overhead.

这就是我所做的和得到的.

import heapq
heap = []

for i in range(10):
    heap.append(i)

heap
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

heapq.heapify(heap)    
heapq.heappush(heap, 10)    
heap
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

heapq.heappop(heap)
0    
heap
[1, 3, 2, 7, 4, 5, 6, 10, 8, 9] <<< Why the list does not remain sorted?

heapq.heappushpop(heap, 11)
1
heap
[2, 3, 5, 7, 4, 11, 6, 10, 8, 9] <<< Why is 11 put between 4 and 6?

因此,正如您所看到的那样,“堆”列表根本没有排序,实际上,添加和删除项目的次数越多,它就越混乱.推动价值取无法解释的位置.
到底是怎么回事？

解决方法:

heapq模块维护堆不变量,这与按排序顺序维护实际列表对象不同.

引自heapq documentation：

Heaps are binary trees for which every parent node has a value less than or equal to any of its children. This implementation uses arrays for which heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2] for all k, counting elements from zero. For the sake of comparison, non-existing elements are considered to be infinite. The interesting property of a heap is that its smallest element is always the root, heap[0].

这意味着找到最小的元素(只需要使用heap [0])非常有效,这对于优先级队列来说非常有用.之后,接下来的2个值将比第1个更大(或相等),之后的4个将大于它们的“父”节点,然后接下来的8个更大,等等.

您可以在Theory section of the documentation中阅读有关数据结构背后的理论的更多信息.您还可以观看this lecture from the MIT OpenCourseWare Introduction to Algorithms course,它以一般术语解释算法.

堆可以非常有效地转回到排序列表中：

def heapsort(heap):
    return [heapq.heappop(heap) for _ in range(len(heap))]

只需从堆中弹出下一个元素即可.然而,使用sorted(heap)应该更快,因为Python的排序使用的TimSort算法将利用堆中已经存在的部分排序.

如果您只对最小值或前n个最小值感兴趣,则使用堆,特别是如果您持续对这些值感兴趣的话;添加新项目并删除最小项目确实非常有效,比每次添加值时使用列表更有效.

内容总结

以上是互联网集市为您收集整理的什么是Python的heapq模块？全部内容，希望文章能够帮你解决什么是Python的heapq模块？所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端