专栏首页疯狂软件李刚Python的堆操作,是不是要掌握一下

Python的堆操作,是不是要掌握一下

导读

Python的强大并不在于它的语法,而在于它的库,当你对各种数据结构感到苦恼时,Python提供了各种开箱即用的数据结构。

Python提供了关于堆的操作,下面先简单介绍有关堆的概念。

假设有n个数据元素的序列k0, k1,…, kn-1,当且仅当满足如下关系时,可以将这组数据称为小顶堆(小根堆)。

ki ≤ k2i+1且ki ≤ k2i+2(其中i=0, 2,…,(n−1)/2)

或者满足如下关系时,可以将这组数据称为大顶堆(大根堆)。

ki ≥ k2i+1且ki ≥ k2i+2(其中i=0, 2,…,(n-1)/2)

对于满足小顶堆的数据序列k0, k1,…, kn-1,如果将它们顺序排成一棵完全二叉树,则此树的特点是:树中所有节点的值都小于其左、右子节点的值,此树的根节点的值必然最小。反之,对于满足大顶堆的数据序列k0, k1,…, kn-1,如果将它们顺序排成一棵完全二叉树,则此树的特点是:树中所有节点的值都大于其左、右子节点的值,此树的根节点的值必然最大。

通过上面介绍不难发现,小顶堆的任意子树也是小顶堆,大顶堆的任意子树还是大顶堆。

Python提供的是基于小顶堆的操作,因此Python可以对list中的元素进行小顶堆排列,这样程序每次获取堆中元素时,总会取得堆中最小的元素。

例如,判断数据序列9, 30, 49, 46, 58, 79是否为堆,可以将其转换为一棵完全二叉树,如图1所示。

图1 完全二叉树

在图1中,每个节点上的灰色数字代表该节点数据在底层数组中的索引。图1所示的完全二叉树完全满足小顶堆的特征,每个父节点的值总小于或等于它的左、右子节点的值。

Python并没有提供“堆”这种数据类型,它是直接把列表当成堆处理的。Python提供的heapq包中有一些函数,当程序用这些函数来操作列表时,该列表就会表现出“堆”的行为。

在交互式解释器中先导入heapq包,然后输入heapq.__all__命令来查看heapq包下的全部函数,可以看到如下输出结果。

>>> heapq.__all__
['heappush', 'heappop', 'heapify', 'heapreplace', 'merge', 'nlargest', 'nsmallest', 'heappushpop']

上面这些函数就是执行堆操作的工具函数,这些函数的功能大致如下。

  • heappush(heap, item):将item元素加入堆。
  • heappop(heap):将堆中最小元素弹出。
  • heapify(heap):将堆属性应用到列表上。
  • heapreplace(heap, x):将堆中最小元素弹出,并将元素x入堆。
  • merge(*iterables, key=None, reverse=False):将多个有序的堆合并成一个大的有序堆,然后再输出。
  • heappushpop(heap, item):将item入堆,然后弹出并返回堆中最小的元素。
  • nlargest(n, iterable, key=None):返回堆中最大的n个元素。
  • nsmallest(n, iterable, key=None):返回堆中最小的n个元素。

下面程序示范了这些函数的用法。

from heapq import *
my_data = list(range(10))
my_data.append(0.5)
# 此时my_data依然是一个list列表
print('my_data的元素:', my_data)
# 对my_data应用堆属性
heapify(my_data) 
print('应用堆之后my_data的元素:', my_data)
heappush(my_data, 7.2)
print('添加7.2之后my_data的元素:', my_data)

上面程序开始创建了一个list列表,接下来程序调用heapify()函数对列表执行堆操作,执行之后看到my_data的元素顺序如下。

应用堆之后my_data的元素:[0, 0.5, 2, 3, 1, 5, 6, 7, 8, 9, 4]

这些元素看上去是杂乱无序的,但其实并不是,它完全满足小顶堆的特征。我们将它转换为完全二叉树,可以看到如图2所示的效果。

图2 小顶堆对应的完全二叉树

当程序再次调用heappush(my_data, 7.2)向堆中加入一个元素之后,输出该堆中元素,可以看到如下输出结果。

添加7.2之后my_data的元素:[0, 0.5, 2, 3, 1, 5, 6, 7, 8, 9, 4, 7.2]

此时将它转换为完全二叉树,可以看到如图3所示的效果。

图3 添加7.2之后的小顶堆对应的完全二叉树

接下来程序尝试从堆中弹出两个元素。

# 弹出堆中最小的元素
print(heappop(my_data)) # 0
print(heappop(my_data)) # 0.5
print('弹出两个元素之后my_data的元素:', my_data)

上面三行代码的输出如下:

0
0.5
弹出两个元素之后my_data的元素:[1, 3, 2, 7, 4, 5, 6, 7.2, 8, 9]

从最后输出的my_data的元素来看,此时my_data的元素依然满足小顶堆的特征。

下面代码示范了replace()函数的用法。

# 弹出最小的元素,压入指定元素
print(heapreplace(my_data, 8.1))
print('执行replace之后my_data的元素:', my_data)

执行上面两行代码,可以看到如下输出结果。

1
执行replace之后my_data的元素:[2, 3, 5, 7, 4, 8.1, 6, 7.2, 8, 9]

也可以测试通过nlargest()、nsmallest()来获取最大、最小的n个元素,代码如下。

print('my_data中最大的3个元素:', nlargest(3, my_data))
print('my_data中最小的4个元素:', nsmallest(4, my_data))

运行上面程序,可以看到如下输出结果。

my_data中最大的3个元素:[9, 8.1, 8]
my_data中最小的4个元素:[2, 3, 4, 5]

通过上面程序不难看出,Python的heapq包中提供的函数,其实就是提供对排序算法中“堆排序”的支持。Python通过在底层构建小顶堆,从而对容器中的元素进行排序,以便程序能快速地获取最小、最大的元素,因此使用起来非常方便。

提示

当程序要获取列表中最大的n个元素,或者最小的n个元素时,使用堆能缓存列表的排序结果,因此具有较好的性能。

本文分享自微信公众号 - 疯狂软件李刚(fkbooks),作者:疯狂软件李刚

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-08-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python的双端队列deque

    Python的强大并不在于它的语法,而在于它的库,当你对各种数据结构感到苦恼时,Python提供了各种开箱即用的数据结构。

    疯狂软件李刚
  • 快速学会Python tkinter的Pack布局

    GUI编程就相当于小孩子搭积木,每个积木块应该放在哪里?每个积木块显示为多大?也就是这些大小和位置都需要进行管理,而布局管理器正是负责管理各组件的大小和位置,此...

    疯狂软件李刚
  • 一小时掌握方法引用和构造器引用

    Java Lambda表达式是很常用的语法,Lambda表达式进一步简化就可写成方法引用和构造器引用。

    疯狂软件李刚
  • 简单算法之冒泡排序

    外层循环控制循环次数,内层循环控制比对元素的个数,因为冒泡排序是两两比对,五个元素的数组只需要比对四次,因为最后一个元素没有可比对的元素,内层循环判断条件j <...

    萬物並作吾以觀復
  • Python运行时动态查看进程内部信息

    kongxx
  • JDK源码阅读(三):ArrayList源码解析

    一般来讲文章开始应该先介绍一下说下简介。这里就不介绍了 如果你不知道 ArrayList 是什么的话就没必要在看了。大致讲一下一些常用的方法

    乱敲代码
  • JDK源码阅读(三):ArrayList源码解析

    一般来讲文章开始应该先介绍一下说下简介。这里就不介绍了 如果你不知道 ArrayList 是什么的话就没必要在看了。大致讲一下一些常用的方法

    码农小胖哥
  • 【DB笔试面试424】SQL Server哪类视图是可以更新的?请举例说明。

    可以在视图上创建INSTEAD OF触发器,从而使视图可更新。当对一个定义了INSTEAD OF触发器的视图执行操作的时候,实际上执行的是触发器中定义的操作,而...

    小麦苗DBA宝典
  • Selenium系列(一) - 详细解读8种元素定位方式

    https://www.cnblogs.com/poloyy/category/1680176.html

    小菠萝测试笔记
  • 怎样的版本历史才是一个好的版本历史

    子勰

扫码关注云+社区

领取腾讯云代金券