首页 > 编程语言 >【Python Cookbook】S01E03 找到最大最小的N个元素

【Python Cookbook】S01E03 找到最大最小的N个元素

时间:2024-05-29 20:00:44浏览次数:24  
标签:heapq S01E03 idx 23 Python 索引 heap Cookbook 节点

目录

问题

如何在一个集合中找到最大或最小的 N 个元素?

解决方案

使用 heapq 模块。

pip install heapq

heapq 模块中,有 nlargest() 以及 nsmallest() 两个函数:

import heapq

nums = [1, 8, 23, 2, 7, -4, 8, 18, 42, 37]
print(heapq.nlargest(3, nums))
print(heapq.nsmallest(3, nums))

在这里插入图片描述

# nlargest函数结构
nlargest(n, arr, key)		# 其中n为取出的数量,arr为数组
# nsmallest函数结构
nsmallest(n, arr, key)

而由于这两个函数 nlargest() nsmallest 都接受一个参数 key,有了这个参数,就可以允许它们工作在更加复杂的数据结构之中。

import heapq

profolio = [
    {"name":"IBM", "shares": 100, "price": 91.1},
    {"name":"AAPL", "shares": 50, "price": 543.22},
    {"name":"FB", "shares": 200, "price": 21.09},
    {"name":"HPQ", "shares": 35, "price": 31.75},
    {"name":"ACME", "shares": 75, "price": 115.65}
]

cheap = heapq.nsmallest(3, profolio, key=lambda s:s['price'])
print(cheap)

在这里插入图片描述

讨论

如果寻找集合 A A A 中最大最小的 N N N 个元素,且 N < < l e n ( A ) N<<len(A) N<<len(A),那么使用下述方案可以提供更好的性能。

首先函数会在底层将集合转化为列表,元素会以堆的顺序排列。

import heapq

nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
heap = list(nums)
heapq.heapify(heap)
print(heap)

上述代码 print(heap) 的结果为:

[-4, 2, 1, 23, 7, 2, 18, 23, 42, 37, 8]

在堆数据结构中,父节点和子节点的关系是基于数组的索引来确定的。对于一个给定的节点,其索引为 i i i,它的父节点、左子节点和右子节点的索引可以通过特定的公式计算得出。

而在 Pythonheapq 模块实现的最小堆中,堆是一个列表,且堆属性满足对于所有索引 i i i(除了根节点,其索引为0),都有 h e a p [ i ] > = h e a p [ ( i − 1 ) / / 2 ] heap[i] >= heap[(i-1)//2] heap[i]>=heap[(i−1)//2]

即任何父节点的值都小于或等于其子节点的值。

[-4, 2, 1, 23, 7, 2, 18, 23, 42, 37, 8]

在这个堆中,

  • 索引 0 的元素是 -4,它是根节点,没有父节点。
  • 索引 1 的元素是 2,它的父节点是 -4(索引为 (1-1)//2 = 0)。
  • 索引 2 的元素是 1,它的父节点也是 -4(索引为 (2-1)//2 = 0)。
  • 索引 3 的元素是 23,它的父节点是 2(索引为 (3-1)//2 = 1)。
  • 索引 4 的元素是 7,它的父节点是 2(索引为 (4-1)//2 = 1)。
  • 索引 5 的元素是 2,它的父节点是 1(索引为 (5-1)//2 = 2)。
  • 以此类推,可以找到每个节点的父节点。

同样地,可以找到每个节点的子节点:

  • 索引 0 的 -4 的左子节点是 2(索引为 2*0 + 1 = 1),右子节点是 1(索引为 2*0 + 2 = 2)。
  • 索引 1 的 2 的左子节点是 23(索引为 2*1 + 1 = 3),右子节点是 7(索引为 2*1 + 2 = 4)。
  • 索引 2 的 1 的左子节点是 2(索引为 2*2 + 1 = 5),但没有右子节点(因为索引 2*2 + 2 = 6 处没有元素)。
  • 以此类推,可以找到每个节点的子节点。

Pythonheapq 模块提供了一个 heapify 函数,该函数能够将一个可变的列表转换为最小堆。过程是自动的,但是可以进行模拟:

  1. 首先找到最后一个非叶子节点的索引:
    • 在一个完全二叉树中,最后一个非叶子节点的索引是 len(heap) // 2 - 1
    • 而本列表中, len(nums) = 11,所以最后一个非叶子节点的索引是 11 // 2 - 1 = 4
  2. 从最后一个非叶子节点开始,向上进行堆化(heapify):
    • 对于每个节点,比较它与它的子节点的值。
    • 如果节点的值大于其子节点中的最小值,则交换这个节点与其最小子节点的值。
    • 重复这个过程,直到堆的根节点。
  3. 重复步骤2,直到整个列表满足堆属性。

手动模拟过程:

# 初始列表
heap = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]

# 从最后一个非叶子节点开始,向上进行堆化
last_non_leaf = len(heap) // 2 - 1
for i in range(last_non_leaf, -1, -1):
    # 比较当前节点与其子节点的值,并进行交换
    current = heap[i]
    left_child_idx = 2 * i + 1
    right_child_idx = 2 * i + 2
    smallest = i

    # 如果左子节点存在且小于当前节点,更新最小值索引
    if left_child_idx < len(heap) and heap[left_child_idx] < current:
        smallest = left_child_idx

    # 如果右子节点存在且小于最小值,更新最小值索引
    if right_child_idx < len(heap) and heap[right_child_idx] < heap[smallest]:
        smallest = right_child_idx

    # 如果当前节点不是最小值,交换它们
    if smallest != i:
        heap[i], heap[smallest] = heap[smallest], heap[i]

# 最终的堆
print(heap)

执行上述代码后,我们得到了一个最小堆。这个过程是迭代的,从最后一个非叶子节点开始,向上逐步将每个节点与其子节点进行比较和交换,直到整个列表满足堆属性。

标签:heapq,S01E03,idx,23,Python,索引,heap,Cookbook,节点
From: https://blog.csdn.net/weixin_43098506/article/details/139298770

相关文章

  • python处理EXCEL
    python处理EXCEL在Python中,有多个库可以用来操作Excel文件。其中比较常用的有openpyxl,pandas,xlsxwriter以及xlwings。下面我将分别介绍这些库及其使用方法。一、openpyxl安装pipinstallopenpyxl示例代码fromopenpyxlimportWorkbook,load_workbookfromopenp......
  • Python正则表达式
    语法关于正则表达式的相关知识,大家可以阅读一篇非常有名的博客叫《正则表达式30分钟入门教程》,读完这篇文章后你就可以看懂下面的表格,这是我们对正则表达式中的一些基本符号进行的扼要总结。符号解释示例说明.匹配任意字符b.t可以匹配bat/but/b#t/b1t等\w匹配字母/......
  • python之生成xmind
    今天为啥要说这个呢,因为前几天做接口测试,还要写测试用例,我觉得麻烦,所以我就用了python里面xmind的插件。自动生成了测试用例,数据来源是json。......
  • ChatGPT学习Python系列之Python装饰器
    ChatGPT学习Python系列之Python装饰器网上查询Python装饰器相关资料,质量层次不齐,通过问答形式利用ChatGPT3.5学习了Python装饰器相关的概念及示例,GPT给出的解答和示例代码质量非常高,总结如下。1.什么是python装饰器Python的装饰器是一种功能强大的语法,允许在不修改原始函数代......
  • python处理EXCEL
    !https://zhuanlan.zhihu.com/p/700537143python处理EXCEL在Python中,有多个库可以用来操作Excel文件。其中比较常用的有openpyxl、pandas,以及xlsxwriter。下面我将分别介绍这些库及其使用方法。一、openpyxl安装pipinstallopenpyxl示例代码fromopenpyxlimportWorkbo......
  • Python lambda函数
    Pythonlambda函数Python中的lambda函数,用于创建简洁的匿名函数。Lambda函数通常用于在需要函数作为参数的上下文中,以及在需要临时定义简单函数的地方。下面是一些关于lambda函数的基本知识和用法:1.lambda函数的基本语法lambdaarguments:expressionlambda关键字用于声明......
  • 用Python写一个热点事件追踪的算法
     要编写一个热点事件追踪的算法,首先需要明确算法的主要目标和所需的数据。在这个例子中,我们将基于微博的热度(如点赞数、转发数和评论数)来追踪热点事件。以下是一个简单的Python算法,仅供参考: 1.导入所需库 ```pythonimportrequestsfrombs4importBeautifulSoupimp......
  • Python截取函数
    在Python中,你可以使用切片(slice)来截取字符串、列表和其他序列类型的一部分。以下是一些常见的示例:1.**截取字符串**:```pythons="Hello,World!"substring=s[7:12] #从索引7开始到索引12(不包括12)结束print(substring) #输出:World```2.**使用负数索引截取**......
  • Python数据分析与挖掘实战(6章)
    非原创,仅个人关于《Python数据分析与挖掘实战》的学习笔记窃漏电数据分析导入相关库importwarningsimportmatplotlib.pyplotaspltimportnumpyasnpimportpandasaspdimportxlrd#解决中文乱码plt.rcParams['font.sans-serif']=['SimHei']plt.rcParams['axe......
  • Python中的压缩和解包: '*'、'**'和zip()
    python中*用途广泛,除了在数学运算中作为相乘还可以在其它方便扮演者对数据的解包之用途。*数学运算中的相乘对元组/列表的解包1.星号*可以用于在解包过程中收集多余的值。例如:numbers=(1,2,3,4,5)#解包时使用*收集多余的值a,b,*rest=numbersprint(a)#......