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实现超市扫码仪计费

python实现超市扫码仪计费

python实现超市扫码仪计费的程序主要是使用超市扫码仪扫商品的条形码,读取商品信息,实现计费功能。主要用到的技术是串口通信,数据库的操作,需要的环境包括:python环境,mysql,...

Python Pandas数据中对时间的操作

Python Pandas数据中对时间的操作

Pandas中对 时间 这个属性的处理有非常非常多的操作。 而本文对其中一个大家可能比较陌生的方法进行讲解。其他的我会陆续上传。 应用情景是这样的:考虑到有一个数据集,数据集中有用户注...

使用PyInstaller将Python程序文件转换为可执行程序文件

Windows下采用PyInstall将py文件转换成exe可执行文件 好不容易写完的py文件,想做成exe文件,最开始选择用py2exe,结果生成的exe遇到两个问题, 1. py程序...

Python2.6版本中实现字典推导 PEP 274(Dict Comprehensions)

之前自己也遇到过一次,这段时间在群里也遇到过几次的一个问题 用python2.7写的一段程序,里面用到了字典推导式,但是服务器版本是python2.6,无法运行。 今天查了下关于Dict...

Python读取mp3中ID3信息的方法

本文实例讲述了Python读取mp3中ID3信息的方法。分享给大家供大家参考。具体分析如下: pyid3不好用,常常有不认识的. mutagen不错,不过默认带的easyid3不会读取注...