请选择 进入手机版 | 继续访问电脑版

[python] Python heapq库案例详解

[复制链接]
查看94 | 回复9 | 2021-9-13 12:01:28 | 显示全部楼层 |阅读模式

Python heapq

heapq 库是 Python 标准库之一,提供了构建小顶堆的方法和一些对小顶堆的基本操作方法(如入堆,出堆等),可以用于实现堆排序算法。

堆是一种基本的数据布局 ,堆的布局 是一棵完全二叉树,并且满意 堆积的性子 :每个节点(叶节点除外)的值都大于等于(或都小于等于)它的子节点。

堆布局 分为大顶堆和小顶堆,在 heapq 中利用 的是小顶堆:

  1. 大顶堆:每个节点(叶节点除外)的值都大于等于其子节点的值,根节点的值是全部 节点中最大的。
  2. 小顶堆:每个节点(叶节点除外)的值都小于等于其子节点的值,根节点的值是全部 节点中最小的。

在 heapq 库中,heapq 利用 的数据范例 是 Python 的基本数据范例 list ,要满意 堆积的性子 ,则在这个列表中,索引 k 的值要小于等于索引 2k+1 的值和索引 2k+2 的值(在完全二叉树中,将数据按广度优先插入,索引为k的节点的子节点索引分别为 2k+1 和 2k+2)。在 heapq 库的源码中也有先容 ,可以读一下 heapq 的源码,代码不多。

利用 Python实现堆排序可以参考:https://www.jb51.net/article/222484.htm

完全二叉树的特性可以参考:https://www.jb51.net/article/222487.htm

一、利用 heapq 创建堆

  1. import heapq
  2. array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
  3. heap = []
  4. for num in array:
  5. heapq.heappush(heap, num)
  6. print("array:", array)
  7. print("heap: ", heap)
  8. heapq.heapify(array)
  9. print("array:", array)
复制代码

运行效果 :

  1. array: [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
  2. heap:  [5, 7, 21, 15, 10, 24, 27, 45, 17, 30, 36, 50]
  3. array: [5, 7, 21, 10, 17, 24, 27, 45, 15, 30, 36, 50]
复制代码

heapq 中创建堆的方法有两种:

heappush(heap, num),先创建一个空堆,然后将数据一个一个地添加到堆中。每添加一个数据后,heap 都满意 小顶堆的特性。

heapify(array),直接将数据列表调整成一个小顶堆(调整的原理参考上面堆排序的文章,heapq库已经实现了)。

两种方法实现的效果 会有差异,如上面的代码中,利用 heappush(heap, num) 得到的堆布局 如下。

在这里插入图片形貌

利用 heapify(array)得到的堆布局 如下。

在这里插入图片形貌

不过,这两个效果 都满意 小顶堆的特性,不影响堆的利用 (堆只会从堆顶开始取数据,取出数据后会重新调整布局 )。

二、利用 heapq 实现堆排序

  1. array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
  2. heap = []
  3. for num in array:
  4. heapq.heappush(heap, num)
  5. print(heap[0])
  6. # print(heapq.heappop(heap))
  7. heap_sort = [heapq.heappop(heap) for _ in range(len(heap))]
  8. print("heap sort result: ", heap_sort)
复制代码

运行效果 :

  1. 5
  2. heap sort result:  [5, 7, 10, 15, 17, 21, 24, 27, 30, 36, 45, 50]
复制代码

先将待排序列表中的数据添加到堆中,构造一个小顶堆,打印第一个数据,可以确认它是最小值。然后依次将堆顶的值取出,添加到一个新的列表中,直到堆中的数据取完,新列表就是排序后的列表。

heappop(heap),将堆顶的数据出堆,并将堆中剩余的数据构造成新的小顶堆。

三、获取堆中的最小值或最大值

  1. array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
  2. heapq.heapify(array)
  3. print(heapq.nlargest(2, array))
  4. print(heapq.nsmallest(3, array))
复制代码

运行效果 :

  1. [50, 45]
  2. [5, 7, 10]
复制代码

nlargest(num, heap),从堆中取出 num 个数据,从最大的数据开始取,返回效果 是一个列表(即使只取一个数据)。假如 num 大于等于堆中的数据数目 ,则从大到小取出堆中的全部 数据,不会报错,相称 于实现了降序排序。

nsmallest(num, heap),从堆中取出 num 个数据,从最小的数据开始取,返回效果 是一个列表。

这两个方法除了可以用于堆,也可以直接用于列表,功能一样。

四、利用 heapq合并两个有序列表

  1. array_a = [10, 7, 15, 8]
  2. array_b = [17, 3, 8, 20, 13]
  3. array_merge = heapq.merge(sorted(array_a), sorted(array_b))
  4. print("merge result:", list(array_merge))
复制代码

运行效果 :

  1. merge result: [3, 7, 8, 8, 10, 13, 15, 17, 20]
  2. merge(list1, list2),将两个有序的列表合并成一个新的有序列表,返回结果是一个迭代器。这个方法可以用于归并排序。
复制代码

五、heapq 更换 数据的方法

  1. array_c = [10, 7, 15, 8]
  2. heapq.heapify(array_c)
  3. print("before:", array_c)
  4. # 先 push 再 pop
  5. item = heapq.heappushpop(array_c, 5)
  6. print("after: ", array_c)
  7. print(item)
  8. array_d = [10, 7, 15, 8]
  9. heapq.heapify(array_d)
  10. print("before:", array_d)
  11. # 先 pop 再 push
  12. item = heapq.heapreplace(array_d, 5)
  13. print("after: ", array_d)
  14. print(item)
复制代码

运行效果 :

  1. before: [7, 8, 15, 10]
  2. after:  [7, 8, 15, 10]
  3. 5
  4. before: [7, 8, 15, 10]
  5. after:  [5, 8, 15, 10]
  6. 7
复制代码

heappushpop(heap, num),先将 num 添加到堆中,然后将堆顶的数据出堆。
heapreplace(heap, num),先将堆顶的数据出堆,然后将 num 添加到堆中。

两个方法都是即入堆又出堆,只是次序 不一样,可以用于更换 堆中的数据。具体 的区别可以看代码中的例子。

到此这篇关于Python heapq库案例详解的文章就先容 到这了,更多相干 Python heapq库内容请搜索 脚本之家从前 的文章或继续欣赏 下面的相干 文章盼望 大家以后多多支持脚本之家!


免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复

使用道具 举报

avatar 我爱霍启刚掖 | 2021-9-18 21:49:38 | 显示全部楼层
我就搞不明白了,看帖回帖能死人么,居然只有我这么认真的在回帖!
回复

使用道具 举报

avatar A01祥天科技 | 2021-9-28 19:28:25 | 显示全部楼层
admin楼主,你妈妈喊你回家吃药!
回复

使用道具 举报

avatar 紫色214 | 2021-10-5 23:42:31 | 显示全部楼层
admin楼主,我告诉你一个你不知道的的秘密,有一个牛逼的网站,运动刷步数还是免费刷的,QQ和微信都可以刷,特别好用。访问地址:http://yd.mxswl.com 猫先森网络
回复

使用道具 举报

avatar 成哥337 | 2021-10-8 02:48:05 | 显示全部楼层
admin楼主人气很旺!
回复

使用道具 举报

avatar 龙的传人739 | 2021-10-15 20:56:55 | 显示全部楼层
投admin楼主一票,不用谢哦!
回复

使用道具 举报

赞一个!
回复

使用道具 举报

帖子好乱!
回复

使用道具 举报

最近回了很多帖子,都没人理我!
回复

使用道具 举报

在这个版块混了这么久了,第一次看见这么给你的帖子!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则