python 的heapq和itertools

heapq

官方介绍文档
这个模块提供了对堆队列算法/优先队列算法的实现。此处的堆指的是大顶堆/小顶堆
在python中,使用了数组来实现大顶堆和小顶堆, 假设这个堆为heap

  • 对于小顶堆来说,从0开始计数,所有的第k个元素,都有heap[k] <= heap[2*k+1]heap[k] <= heap[2*k+2], 即根节点小于子节点
  • 对于大顶堆来说则正好相反:heap[k] >= heap[2*k+1]heap[k] >= heap[2*k+2]

heapq中,这里的堆指的是小顶堆,最小元素总是在根节点heap[0]

heapq这个API同教材上的堆算法是不同的,主要在两个方面:

  • 使用0作为起始索引,这样会使得父节点和子节点之间的索引关系变得不那么明显,但是在python中这是很合适的,因为pythonlist使用0作为起始索引。
  • pop方法返回的是最小元素而不是最大元素

heapq方法一览

heap.heappush(heap, item)
# 往一个堆里面push一个元素

heap.heappop(heap)
# 将堆里面的最小元素返回,如果heap是空的话,会引起IndexError

heap.heappushpop(heap, item)
# 先往堆里面推入一个元素,然后将堆中的最小元素pop出来并返回
# 这个方法比先调用和heappush()然后调用heappop()要高效的多

heapq.heapify(x:list)
# 将列表x在 线性时间内 原地转化为堆结构

heapq.heapreplace(heap, item)
# 首先,将堆中的最小元素pop出来,返回
# 然后,将新的item 推入到堆里面,堆的长度不变
# 相当于先调用heappop,再调用heappush, 与heappushpop刚好相反,一般情况下结果是一样的
# 如果想要返回的元素比参数item小,可以用heapq.heappushpop()

heapq.merge(*iterables, key=None, reverse=False)
# 合并两个有序的iter可迭代对象(列表/集合/...)
# 返回的也是一个可迭代对象

heapq.nlargest(n, iterable, key=None)
# 返回可迭代对象iterable里面的前n个最大值
# 返回的是一个列表

heapq.nsmallest(n, iterable, key=None)
# 返回可迭代对象iterable里面的前n个最小值
# 返回的是一个列表


itertools

itertools 是为高效循环而创建的迭代器函数

一般情况下主要使用到的方法有三个:

  • permutations(iterable) --> 创建一个全排列的列表并返回
  • combinations(iterable, count) --> 组合工具:从iterable可迭代对象里面选择count个元素,返回所有的组合方式
  • product(iterableA, iterableB) --> 迪卡尔积
全部评论

相关推荐

01-20 10:59
中北大学 运营
juntenor:这是详历,可不是简历
点赞 评论 收藏
分享
希望被捞的猫头鹰很理智:大概率待遇低怕硕士跑路
点赞 评论 收藏
分享
头像
03-14 11:23
已编辑
北京邮电大学 管理咨询
211勇闯初创小公司头破血流系列3这件事不是发生在我身上的,但前同事们参与创作的积极性空前高涨,为了习惯,还是都采用第一人称的视角来看这出大戏。有一天老板在我们的眼皮底下接了一个电话,最终敲定了去北京出差的时间,下周一。他得意洋洋地说,这单下来保底五百万的流水,如果成了,我们都能得到五位数的提成。这对于一群刚上班的人来说是天大的诱惑,我们经历了周末的无偿加班,把他去北京所需要的文件都准备好了。只是在去北京的周一当天,老板睡过头了。整个上午都没见他的踪影,给他发文件也不会,打电话问问题也不接,直到中午才姗姗来迟。当然,这只是拉开了这场恐怖出差的序幕。只见他来了也不紧不慢的,手指在办公室转了一圈,...
姜大力:补充: 1.五百万的单子根本没有五百万,只是过去展示拼装的产品并简单考察。该项目只是竞标,项目内容是商业街区改造; 2.决策是当天上午10点半左右老板珊珊来迟后突发奇想去北京,中午1点在催促下着急出发,没有任何出差补助; 3.出发之前已经知道进京证不好使了,但还是执意要开车去; 4.实习生实打实连续开了***小事车,非常辛苦,工资在转正后只有两千五; (有疑问会继续补充)
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务