Python heapq使用详解及实例代码

yipeiwu_com5年前Python基础

 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])

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

相关文章

Python 进程之间共享数据(全局变量)的方法

进程之间共享数据(数值型): import multiprocessing def func(num): num.value=10.78 #子进程改变数值的值,主进程跟着改变...

将python依赖包打包成window下可执行文件bat方式

1、 打开一个记事本,将需要安装的第三方python依赖包写入文件,比如:需要安装urllib3、flask、bs4三个python库(替换成你想要安装的库,每个库之间用空格隔开),输入...

在django中图片上传的格式校验及大小方法

如下所示: Uploadfiles = request.FILES.get('参数', '') for i in Uploadfiles : # 图片大小的属性 i...

Python内置函数之filter map reduce介绍

Python内置了一些非常有趣、有用的函数,如:filter、map、reduce,都是对一个集合进行处理,filter很容易理解用于过滤,map用于映射,reduce用于归并. 是Py...

python 3.6.4 安装配置方法图文教程

python 3.6.4 安装配置方法图文教程

今天补一下关于如何安装Python的操作步骤: 我的系统是我win系统 64 位 1.第一步先去python的官方网站下载python的安装包:地址 根据自己的系统选择对应的...