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
投稿猜你喜欢
一个单步的动作，用了这个脚本，就可以重复执行100遍1000遍。上面就是一个路径描边100遍的效果，吼吼~ 不知道大家明白用处没有？（以前老- 子节点部分选中时父节点也选中如果需求是：选中任何一个子节点都默认选择父节点，怎么办？其实，element-ui也提供了方案，常规下，如果子节
- 前言近来chatGPT挺火的，也试玩了一下，确实挺有意思。这里记录一下在Python中如何去使用chatGPT。本篇文章的实现100％基于
- /*Bresenham画圆算法*/var arc = function(x0,y0,r){/*起点坐标x0,y
- 本文实例讲述了python从sqlite读取并显示数据的方法。分享给大家供大家参考。具体实现方法如下：import cgi, os, sys
- #-*- coding:utf-8 -*- from win32com.client import Dispatch import time
- 本文为大家分享了python链表的基础概念和基础用法，供大家参考，具体内容如下一、什么是链表链表是由多个不同的节点组成，每个节点通过指针区域
- def quick_sort(ls): return [] if ls == [] else quick_sort([y for y in
- 废话真的一句也不想多说，直接看代码吧！# -*- coding: utf-8 -*- import numpy from sklearn i
- 这篇文章主要介绍了python如果快速判断数字奇数偶数,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值,需要的朋
- python ThreadPoolExecutor线程池的工作线程中出现异常时，主线程不会捕获异常。解决方法1：直接在需要执行的任务方法中添
- 出图是项目里常见的任务，有的项目甚至会要上百张图片，所以批量出土工具很有必要。arcpy.mapping就是ArcGIS里的出图模块，能快速
- 1．不装入数据库而启动事例 可以不装入数据库而启动事例，一般是在数据库才创建时才可以这样做：STARTUP NOMOUNT2.启动事例并装入
- 1.示例树的一些属性：层次性：树是按层级构建的，越笼统就越靠近顶部，越具体则越靠近底部。一个节点的所有子节点都与另一个节点的所有子节点无关。
- 修改models效果如下class EmailVerifyRecord(models.Model): code = models
- 大家一定使用过 phpmyadmin 里面的数据库导入，导出功能，非常方便。但是在实际应用中，我发现如下几个问题： 1、数据库超过一定尺寸，
- 本文实例讲述了Python基于回溯法子集树模板解决选排问题。分享给大家供大家参考，具体如下：问题从n个元素中挑选m个元素进行排列，每个元素最
- 一个ASP文件通常包含HTML标签，有时和一个HTML文件非常类似。然而，ASP文件（除了包含HTML标签外），还可以包括服务器的脚本程序，
- os.systemsystem方法会创建子进程运行外部程序，方法只返回外部程序的运行结果。这个方法比较适用于外部程序没有输出结果的情况。im
- 利用可视化探索图表1.数据可视化与探索图数据可视化是指用图形或表格的方式来呈现数据。图表能够清楚地呈现数据性质， 以及数据间或属性间的关系，
