从一个集合中查找最大最小的N个元素——Python heapq 堆数据结构

Top N问题在搜索引擎、推荐系统领域应用很广, 如果用我们较为常见的语言,如C、C++、Java等,代码量至少也得五行,但是用Python的话,只用一个函数就能搞定,只需引入heapq(堆队列)这个数据结构即可。今天偶然看到这个库,特意记下之。

先看一个例子:

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

是不是很简洁? 我们具体来看一下具体的函数定义。heapq有很多函数,最为堆,队列,可想而知,也就是那些push,pop之类的操作,详细请看官方文档:https://docs.python.org/2/library/heapq.html,在这里,我们只看Top N的两个函数,其他函数在用到的时候查看文档就好了。

1)、heapq.nlargest(n, iterable[, key])

从迭代器对象iterable中返回前n个最大的元素列表,其中关键字参数key用于匹配是字典对象的iterable,用于更复杂的数据结构中。

2)、heapq.nsmallest(n, iterable[, key])

从迭代器对象iterable中返回前n个最小的元素列表,其中关键字参数key用于匹配是字典对象的iterable,用于更复杂的数据结构中。

关于第三个参数的应用,我们来看一个例子就明白了。

 1 >>> portfolio = [
 2     {'name': 'IBM', 'shares': 100, 'price': 91.1},
 3     {'name': 'AAPL', 'shares': 50, 'price': 543.22},
 4     {'name': 'FB', 'shares': 200, 'price': 21.09},
 5     {'name': 'HPQ', 'shares': 35, 'price': 31.75},
 6     {'name': 'YHOO', 'shares': 45, 'price': 16.35},
 7     {'name': 'ACME', 'shares': 75, 'price': 115.65}
 8 ]
 9 ... ... ... ... ... ... ... >>> 
10 >>> cheap = heapq.nsmallest(3, portfolio, key=lambda s: s['price'])
11 >>> print cheap
12 [{'price': 16.35, 'name': 'YHOO', 'shares': 45}, {'price': 21.09, 'name': 'FB', 'shares': 200}, {'price': 31.75, 'name': 'HPQ', 'shares': 35}]
13 >>> expensive = heapq.nlargest(3, portfolio, key=lambda s: s['price'])
14 >>> print expensive
15 [{'price': 543.22, 'name': 'AAPL', 'shares': 50}, {'price': 115.65, 'name': 'ACME', 'shares': 75}, {'price': 91.1, 'name': 'IBM', 'shares': 100}]
16 >>> 

从例子中可以看出,key匹配了portfolio中关键字为‘price’的一行。 到此为止,关于如何应用heapq来求Top N问题,相比通过上面的例子讲解,已经较为熟悉了。现在有几个需要注意的地方:

1)heapq.heapify(iterable):可以将一个列表转换成heapq

2)在Top N问题中,如果N=1,则直接用max(iterable)/min(iterable)即可。

3)如果N很大,接近集合元素,则为了提高效率,采用sort+切片的方式会更好,如:

求最大的N个元素:sorted(iterable, key=key, reverse=True)[:N]

求最小的N个元素:sorted(iterable, key=key)[:N]

1 >>> nums = [1,8,2,23,7,-4,18,23,42,37,2]
2 >>> max(nums)
3 42
4 >>> min(nums)
5 -4
6 >>> print sorted(nums, reverse=True)[:3]
7 [42, 37, 23]
8 >>> print sorted(nums)[:3]
9 [-4, 1, 2]

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

数据结构学习笔记【持续更新】

数据结构概述:   定义:     我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到保存到主存储器(内存)中,     以及在此基础上为实...

23630
来自专栏程序员互动联盟

java到底和C++有啥区别?

作为一名C++程序员,我们早已掌握了面向对象程序设计的基本概念,而且Java的语法无疑是非常熟悉的。事实上,Java本来就是从C++衍生出来的。 然而,C++和...

41260
来自专栏Java面试通关手册

最最最常见的Java面试题总结——第二周

String类中使用字符数组:private final char value[]保存字符串,所以String对象是不可变的。StringBuilder与Str...

13520
来自专栏web前端教室

浅谈数据结构 - 字典

浅淡,真的是很浅。Orz.. 先摆出定义,这里的字典是啥样的? 是以键-值对形式保存数据的一种结构。 现实中比较典型的例子,就是以前的电话本。你想找一个单位的电...

205100
来自专栏java一日一条

Java集合框架综述

近被陆陆续续问了几遍HashMap的实现,回答的不好,打算复习复习JDK中的集合框架,并尝试分析其源码,这么做一方面是这些类非常实用,掌握其实现能更好的优化我们...

11440
来自专栏小俊博客

Nginx的location规则迷之匹配

Nginx,一个改变世界的软件,其作者是一个俄罗斯人,俗称毛子,在国人的印象中,是一群晚饭后牵着大灰熊在小区楼下散步的彪汉。能写出这般顺滑的软件,可谓是心有猛虎...

74320
来自专栏GreenLeaves

C# 泛型

1、泛型的优势 在日常开发中,我们经常会开发一些特殊的功能,而这个功能适用于多个类型(比如string,int等多种类型),最简单的做法是给每种类型都做一个实现...

205100
来自专栏编程

Python函数之匿名函数

各位小伙伴,周五快乐! 今天是2017年最后一个工作日,大家都在忙碌些什么呢? 今天我们要讲的是Python函数中的匿名函数 好像函数中的分类及说法很多,但是大...

21960
来自专栏java一日一条

Java集合框架综述

近被陆陆续续问了几遍HashMap的实现,回答的不好,打算复习复习JDK中的集合框架,并尝试分析其源码,这么做一方面是这些类非常实用,掌握其实现能更好的优化我们...

10410
来自专栏奇点大数据

Scala语言学习笔记一

Scala是一门小众的语言,但是作者因为工作原因要以Spark作为工作中的一个重心,而Spark采用了Scala语言编写,于是萌生了认真学习Scala的念头,在...

37740

扫码关注云+社区

领取腾讯云代金券