python使用heapq实现小顶堆(TopK大)/大顶堆(BtmK小)

2024-03-13 17:38

本文主要是介绍python使用heapq实现小顶堆(TopK大)/大顶堆(BtmK小),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

参考链接

https://www.coder4.com/archives/3844

求一个数列前K大数的问题经常会遇到,在程序中一般用小顶堆可以解决,下面的代码是使用python的heapq实现的小顶堆示例代码:

    # !/usr/bin/env python# -*- coding:gbk -*-import sysimport heapqclass TopKHeap(object):def __init__(self, k):self.k = kself.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))])]def main():list_num = [1, 2, 3, 4, 5, 6, 7, 8, 9]th = TopKHeap(5)for i in list_num:th.push(i)print th.topk()if __name__ == "__main__":main()

python的heapq在实现的时候,没有像STL或者Java可以传入比较函数,具体的原因可以参考参考文档给出的链接。

因此有些人想出了比较trick的思路。一句话概括如下:

push(e)改为push(-e),pop(e)为-pop(e),也就是说存入和取出的数都是相反数,其他逻辑和TopK相同。(点赞)

实现用户自定义的比较函数,允许elem是一个tuple,按照tuple的第一个元素进行比较,所以可以把tuple的第一个元素作为我们的比较的key。

英文原话:

The heapq documentation suggests that heap elements could be tuples in which the first element is the priority and defines the sort order.

    import heapqclass MyHeap(object):def __init__(self, initial=None, key=lambda x:x):self.key = keyif initial:self._data = [(key(item), item) for item in initial]heapq.heapify(self._data)else:self._data = []def push(self, item):heapq.heappush(self._data, (self.key(item), item))def pop(self):return heapq.heappop(self._data)[1]

这篇关于python使用heapq实现小顶堆(TopK大)/大顶堆(BtmK小)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/805651

相关文章

Python基于wxPython和FFmpeg开发一个视频标签工具

《Python基于wxPython和FFmpeg开发一个视频标签工具》在当今数字媒体时代,视频内容的管理和标记变得越来越重要,无论是研究人员需要对实验视频进行时间点标记,还是个人用户希望对家庭视频进行... 目录引言1. 应用概述2. 技术栈分析2.1 核心库和模块2.2 wxpython作为GUI选择的优

使用Sentinel自定义返回和实现区分来源方式

《使用Sentinel自定义返回和实现区分来源方式》:本文主要介绍使用Sentinel自定义返回和实现区分来源方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Sentinel自定义返回和实现区分来源1. 自定义错误返回2. 实现区分来源总结Sentinel自定

Pandas使用SQLite3实战

《Pandas使用SQLite3实战》本文主要介绍了Pandas使用SQLite3实战,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学... 目录1 环境准备2 从 SQLite3VlfrWQzgt 读取数据到 DataFrame基础用法:读

JSON Web Token在登陆中的使用过程

《JSONWebToken在登陆中的使用过程》:本文主要介绍JSONWebToken在登陆中的使用过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录JWT 介绍微服务架构中的 JWT 使用结合微服务网关的 JWT 验证1. 用户登录,生成 JWT2. 自定义过滤

Java中StopWatch的使用示例详解

《Java中StopWatch的使用示例详解》stopWatch是org.springframework.util包下的一个工具类,使用它可直观的输出代码执行耗时,以及执行时间百分比,这篇文章主要介绍... 目录stopWatch 是org.springframework.util 包下的一个工具类,使用它

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

opencv图像处理之指纹验证的实现

《opencv图像处理之指纹验证的实现》本文主要介绍了opencv图像处理之指纹验证的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学... 目录一、简介二、具体案例实现1. 图像显示函数2. 指纹验证函数3. 主函数4、运行结果三、总结一、

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

Springboot处理跨域的实现方式(附Demo)

《Springboot处理跨域的实现方式(附Demo)》:本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.

springboot security使用jwt认证方式

《springbootsecurity使用jwt认证方式》:本文主要介绍springbootsecurity使用jwt认证方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录前言代码示例依赖定义mapper定义用户信息的实体beansecurity相关的类提供登录接口测试提供一