Python heapq使用详解及实例代码
作者:纯臻 发布时间:2023-03-07 14:36:56
标签: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
投稿
猜你喜欢
- 解决的问题需要将数组(list)或元组(tuple)中的元素导出到N个变量中。解决的方案任何序列都可以通过简单的变量赋值方式将其元素分配到对
- 不使用int()函数的情况下把字符串转换为数字,如把字符串"12345"转换为数字12345。方法一:利用str函数既然
- 变量类型ECMAScript变量可能包含两种不同类型的数据值:基本类型和引用类型。基本类型基本类型指的是简单的数据段,5种基本数据类型:un
- asp 中处理文件上传以及删除时常用的自定义函数:删除文件,建立目录的程序,根据原文件名生成新的随机文件名,CMS替换函数,将所有开始,结束
- PHP getNamespaces() 函数实例返回 XML 文档中使用的命名空间:<?php $xml=<<<XM
- 本文将介绍使用mutable对象作为Python函数参数默认值潜在的危害,以及其实现原理和设计目的陷阱重现我们就用实际的举例来演示我们今天所
- import Exception# except 在捕获错误异常的时候 是要根据具体的错误类型来捕获的# 用一个块 可以捕获多个不同类型的异
- 1.认识数组数组就是某类数据的集合,数据类型可以是整型、字符串、甚至是对象Javascript不支持多维数组,但是因为数组里面可以包含对象(
- PHP hex2bin() 函数实例把十六进制值转换为 ASCII 字符:<?php echo hex2bin("48656
- 1. 排序有什么用“排序”这个专业名词原本是来源于计算机程序操作中的,是一种很常见的算法设计,当然,对交互设计来说,探讨冒泡排序和堆排序之间
- 根据国务院文件,5.19-5.21为全国哀悼日,在此期间,全国和各驻外机构下半旗志哀,停止公共娱乐活动,外交部和我国驻外使领馆设立吊唁簿。5
- 虽然现在有许多网页制作工具能让您轻松地完成工作,但如果使用HTML则可以得到更大控制权,下面介绍几个小技巧。1.使用语句来控制文字排版比用好
- 元组的结构在这一小节当中主要介绍在 python 当中元组的数据结构:typedef struct { PyObj
- 本文分别介绍了安装python2和python3的详细方法,分享给大家。一、Windows系统很多童鞋问之前的教程怎么没有介绍安装pytho
- 背景:这个库的安装不是像其他的一样的直接使用 pip install XXX的形式,而是使用原始的Git方式1、apex这是NVIDIA开发
- Pytorch:dtype不一致RuntimeError: Expected object of scalar type Double bu
- go简单代码反汇编用简单的代码用以分析go的调用约定及多返回值的返回方式。package mainfunc vals(c, d int) (
- 如何用POP3接收电子邮件?POP3大行其道,我看见朋友已经用Jmail和POP3接收邮件了。该如何做?以Jmail4.1为例,我们演示一下
- 首先,与其他语言不同,JS的效率很大程度是取决于JS engine的效率。除了引擎实现的优劣外,引擎自己也会为一些特殊的代码模式采取一些优化
- 代码如下:'其中注释中有 ###的需要用户设置 '其中注释中有 参数传递 ** 的 说明要通过参数 传递。'定义变量