Python heapq使用详解及实例代码

yipeiwu_com6年前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实现网站注册验证码生成类

本文实例为大家分享了Python网站注册验证码生成类的具体代码,供大家参考,具体内容如下 # -*- coding:utf-8 -*- ''' Created on 2017年4月7...

opencv3/Python 稠密光流calcOpticalFlowFarneback详解

opencv3/Python 稠密光流calcOpticalFlowFarneback详解

光流是由物体或相机的运动引起的图像对象在两个连续帧之间的视在运动模式.光流方法计算在t和 t+Δtt+Δt时刻拍摄的两个图像帧之间的每个像素的运动位置。这些方法被称为差分,因为它们基于图...

解决Python2.7中IDLE启动没有反应的问题

解决Python2.7中IDLE启动没有反应的问题

安装Python2.7后,它自带一个编辑器IDLE,但是使用几次之后出现启动不了的情况,可做如下操作。 Windows操作系统下,使用快捷键 win+R 启动“运行”对话框,输入下面的路...

将pandas.dataframe的数据写入到文件中的方法

将pandas.dataframe的数据写入到文件中的方法

导入实验常用的python包。如图2所示。 【import pandas as pd】pandas用来做数据处理。【import numpy as np】numpy用来做高维度矩阵运算....

详解python中的 is 操作符

大家可以与Java中的 == 操作符相互印证一下,加深一下对引用和对象的理解。原问题: Python为什么直接运行和在命令行运行同样语句但结果却不同,他们的缓存机制不同吗? 其实...