Python heapq使用详解及实例代码

 Python heapq 详解

Python有一个内置的模块，heapq标准的封装了最小堆的算法实现。下面看两个不错的应用。

小顶堆（求TopK大）

话说需求是这样的： 定长的序列，求出TopK大的数据。

import heapq
import random

class TopkHeap(object):
  def __init__(self, k):
    self.k = k
    self.data = []

  def Push(self, elem):
    if len(self.data) < self.k:
      heapq.heappush(self.data, elem)
    else:
      topk_small = self.data[0]
      if elem > topk_small:
        heapq.heapreplace(self.data, elem)

  def TopK(self):
    return [x for x in reversed([heapq.heappop(self.data) for x in xrange(len(self.data))])]

if __name__ == "__main__":
  print "Hello"
  list_rand = random.sample(xrange(1000000), 100)
  th = TopkHeap(3)
  for i in list_rand:
    th.Push(i)
  print th.TopK()
  print sorted(list_rand, reverse=True)[0:3]

大顶堆（求BtmK小）

这次的需求变得更加的困难了：给出N长的序列，求出BtmK小的元素，即使用大顶堆。

算法实现的核心思路是：将push(e)改为push(-e)、pop(e)改为-pop(e)。

class BtmkHeap(object):
  def __init__(self, k):
    self.k = k
    self.data = []

  def Push(self, elem):
    # Reverse elem to convert to max-heap
    elem = -elem
    # Using heap algorighem
    if len(self.data) < self.k:
      heapq.heappush(self.data, elem)
    else:
      topk_small = self.data[0]
      if elem > topk_small:
        heapq.heapreplace(self.data, elem)

  def BtmK(self):
    return sorted([-x for x in self.data])

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

赞 (0)

相关推荐

  • python学习之面向对象【入门初级篇】

    python学习之面向对象【入门初级篇】

    前言 最近在学习Python的面向对象编程,以前是没有接触过其它的面向对象编程的语言,因此学习这一部分是相当带劲的,这里也总结一下. 概述 python支持多种编程范式:面向过程.面向对象.面向切面(装饰器部分)等. 面向过程:根据业务逻辑从上到下写垒代码 函数式:将某功能代码封装到函数中,日后便无需重复编写,仅调用函数即可 面向对象:对函数进行分类和封装,让开发"更快更好更强..." OOP思想 面向对象的基本哲学:世界由具有各自运动规律和内部状态的对象组成,对象之间相互作用和通讯构

  • 详解Python中heapq模块的用法

    详解Python中heapq模块的用法

    heapq 模块提供了堆算法.heapq是一种子节点和父节点排序的树形数据结构.这个模块提供heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2].为了比较不存在的元素被人为是无限大的.heap最小的元素总是[0]. 打印 heapq 类型 import math import random from cStringIO import StringIO def show_tree(tree, total_width=36, fill=' '): ou

  • Python 数据结构之队列的实现

    Python 队列 Queue 队列是一种先进先出(FIFO)的数据类型, 新的元素通过 入队 的方式添加进 Queue 的末尾, 出队 就是从 Queue 的头部删除元素. 用列表来做 Queue: queue = [] # 初始化一个列表数据类型对象, 作为一个队列 def enQ(): # 定义一个入栈方法 queue.append(raw_input('Enter New String: ').strip()) # 提示输入一个入队的 String 对象, 调用 Str.strip()

  • CentOS6.5 升级 Python 2.7 版本详细介绍

     CentOS6.5 升级 Python 2.7 版 概要 CentOS 6.5中预安装了Python-2.6.6,其比较新的Python-2.7.9(CentOS 7预装版本)主要区别在于新版本的Python导入了更丰富的模块功能.对于初学者而言这一般不会有太大的影响,相对而言这些新模块在某些特定的编译环境下却是不可或缺的.例如:使用Devstack all-in-one模式进行安装OpenStack开发调试平台,需要Python-2.7及以上的支持,这样可以省去很多缺失模块的麻烦. - 软件

  • 在linux的终端退出python命令行的方法

    如下所示: Python 2.7.7 (default, Jun 3 2014, 01:46:20) [GCC 4.9.0 20140521 (prerelease)] on linux2Type "help", "copyright", "credits" or "license" for more information.>>> quitUse quit() or Ctrl-D (i.e. EOF) to

  • Python中struct模块对字节流/二进制流的操作教程

    Python中struct模块对字节流/二进制流的操作教程

    前言 最近使用Python解析IDX文件格式的MNIST数据集,需要对二进制文件进行读取操作,其中我使用的是struct模块.查了网上挺多教程都写的挺好的,不过对新手不是很友好,所以我重新整理了一些笔记以供快速上手. 注:教程中以下四个名词同义:二进制流.二进制数组.字节流.字节数组 快速上手 在struct模块中,将一个整型数字.浮点型数字或字符流(字符数组)转换为字节流(字节数组)时,需要使用格式化字符串fmt告诉struct模块被转换的对象是什么类型,比如整型数字是'i',浮点型数字是'f

  • 解决python2.7用pip安装包时出现错误的问题

    解决python2.7用pip安装包时出现错误的问题

    最近在使用pip安装包的的时候出现下面错误 UnicodeEncodeError: 'ascii' codec can't encode character u'\u258f' 查询资料后发现原因是pip安装python包会加载用户目录,用户目录恰好是中文的,ascii不能编码 打开对应的安装目录路径 D:\Python27\Lib\site-packages 新建一个文件 sitecustomize.py 输入下面内容 # encoding=utf8 import sys reload(sys

  • 用python实现简单EXCEL数据统计的实例

    用python实现简单EXCEL数据统计的实例

    任务: 用python时间简单的统计任务-统计男性和女性分别有多少人. 用到的物料:xlrd 它的作用-读取excel表数据 代码: import xlrd workbook = xlrd.open_workbook('demo.xlsx') #打开excel数据表 SheetList = workbook.sheet_names()#读取电子表到列表 SheetName = SheetList[0]#读取第一个电子表的名称 Sheet1 = workbook.sheet_by_index(0)

  • Python 详解基本语法_函数_返回值

    Python 详解基本语法 概要: 函数的返回值是函数重要的组成部分.函数的根本在于实现程序的部分功能,所以很多时候我们需要将函数执行后的结果返回给程序再由程序作出进一步的操作.可以说是函数的返回值令函数与函数之间,函数与主程序之间更加紧密的联系起来. 函数的返回值 在Python的函数中都有一个返回值,默认为None.也可以使用return value语句来定义一个且只能定义一个可为任意类型的返回值.但是我们能够返回一个序列类型的对象,来实现返回多个值的效果. Example: 返回一个Lis

  • Python heapq使用详解及实例代码

     Python heapq 详解 Python有一个内置的模块,heapq标准的封装了最小堆的算法实现.下面看两个不错的应用. 小顶堆(求TopK大) 话说需求是这样的: 定长的序列,求出TopK大的数据. import heapq import random class TopkHeap(object): def __init__(self, k): self.k = k self.data = [] def Push(self, elem): if len(self.data) < self

  • Python 爬虫多线程详解及实例代码

    python是支持多线程的,主要是通过thread和threading这两个模块来实现的.thread模块是比较底层的模块,threading模块是对thread做了一些包装的,可以更加方便的使用. 虽然python的多线程受GIL限制,并不是真正的多线程,但是对于I/O密集型计算还是能明显提高效率,比如说爬虫. 下面用一个实例来验证多线程的效率.代码只涉及页面获取,并没有解析出来. # -*-coding:utf-8 -*- import urllib2, time import thread

  • Python运算符重载详解及实例代码

    Python运算符重载 Python语言提供了运算符重载功能,增强了语言的灵活性,这一点与C++有点类似又有些不同.鉴于它的特殊性,今天就来讨论一下Python运算符重载. Python语言本身提供了很多魔法方法,它的运算符重载就是通过重写这些Python内置魔法方法实现的.这些魔法方法都是以双下划线开头和结尾的,类似于__X__的形式,python通过这种特殊的命名方式来拦截操作符,以实现重载.当Python的内置操作运用于类对象时,Python会去搜索并调用对象中指定的方法完成操作. 类可以

  • Python 实现随机数详解及实例代码

    Python 实现随机数详解及实例代码

    Python3实现随机数 random是用于生成随机数的,我们可以利用它随机生成数字或者选择字符串. random.seed(x)改变随机数生成器的种子seed. 一般不必特别去设定seed,Python会自动选择seed. random.random() 用于生成一个随机浮点数n,0 <= n < 1 random.uniform(a,b) 用于生成一个指定范围内的随机浮点数,生成的随机整数a<=n<=b; random.randint(a,b) 用于生成一个指定范围内的整数,a

  • Python 字典的使用详解及实例代码

    目录 字典长什么样 字典内能放什么 访问字典内容 修改字典内容 删除字典数据 字典内置函数 字典是Python实现散列表数据结构的形式,表现映射的关系,一对一. 字典长什么样 {}这是一个空字典,可以看出字典是由两个花括号组成的. 在看这个{'a':1},这里面装了一对数据,'a'可称为键,1称为值 这个{'键1':'值1', '键2':'值2'}每一对数据 字典内能放什么 字典内的健是唯一的,在字典内所有内容中只存在一个,但值可以重复出现. 健只能是不变的值,比如字符串,数字,元组 值可以随意

  • Python 操作MySQL详解及实例

    Python 操作MySQL详解及实例 使用Python进行MySQL的库主要有三个,Python-MySQL(更熟悉的名字可能是MySQLdb),PyMySQL和SQLAlchemy. Python-MySQL资格最老,核心由C语言打造,接口精炼,性能最棒,缺点是环境依赖较多,安装复杂,近两年已停止更新,只支持Python2,不支持Python3. PyMySQL为替代Python-MySQL而生,纯python打造,接口与Python-MySQL兼容,安装方便,支持Python3. SQLA

  • MyBatis获取数据库自生成的主键Id详解及实例代码

    MyBatis获取数据库自生成的主键Id详解及实例代码 在使用MySQL数据库时我们一般使用数据库的自增主键自动产生主键.如果在插入主表时,我们需要同时插入从表的数据,这时我们通常需要知道主表插入时自动产生的主键Id值. 下面介绍使用MyBatis进行插入时,如何同时获取数据库自生成的主键: 1.XML配置文件 <insert id="insert" parameterType="Person" useGeneratedKeys="true"

  • MySQL 序列 AUTO_INCREMENT详解及实例代码

    MySQL 序列 AUTO_INCREMENT详解及实例代码 MySQL序列是一组整数:1, 2, 3, ...,由于一张数据表只能有一个字段自增主键, 如果你想实现其他字段也实现自动增加,就可以使用MySQL序列来实现. 本章我们将介绍如何使用MySQL的序列. 使用AUTO_INCREMENT MySQL中最简单使用序列的方法就是使用 MySQL AUTO_INCREMENT 来定义列. 实例 以下实例中创建了数据表insect, insect中id无需指定值可实现自动增长. mysql>

  • Java 两种延时thread和timer详解及实例代码

    Java 两种延时thread和timer详解及实例代码 在Java中有时候需要使程序暂停一点时间,称为延时.普通延时用Thread.sleep(int)方法,这很简单.它将当前线程挂起指定的毫秒数.如 try { Thread.currentThread().sleep(1000);//毫秒 } catch(Exception e){} 在这里需要解释一下线程沉睡的时间.sleep()方法并不能够让程序"严格"的沉睡指定的时间.例如当使用5000作为sleep()方法的参数时,线 程

  • Python操作MongoDB详解及实例

    Python操作MongoDB详解及实例 由于需要在页面展示MongoDB库里的数据,所以考虑使用python操作MongoDB,PyMongo模块是Python对MongoDB操作的接口包,所以首页安装pymongo. 1.安装命令 pip install pymongo 2.查询命令: import pymongo # 创建连接 client = pymongo.MongoClient(host="10.0.2.38", port=27017) # 连接probeb库 db = c

随机推荐