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

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

相关文章

Python3学习笔记之列表方法示例详解

前言 本文主要给大家介绍了关于Python3列表方法的相关内容,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍吧。 1 使用[]或者list()创建列表 user =...

python使用Tkinter显示网络图片的方法

本文实例讲述了python使用Tkinter显示网络图片的方法。分享给大家供大家参考。具体实现方法如下: ''' tk_image_view_url_io.py display an...

用python wxpy管理微信公众号并利用微信获取自己的开源数据

用python wxpy管理微信公众号并利用微信获取自己的开源数据

之前了解到itchat 乃至于 wxpy时 是利用tuling聊天机器人的接口。调用接口并保存双方的问答结果可以作为自己的问答词库的一个数据库累计。这些数据可以用于自己训练。 而最近希望...

开始着手第一个Django项目

一但你安装好了python,django和(可选的)数据库及相关库,你就可以通过创建一个project,迈出开发django应用的第一步。 项目 是 Django 实例的一系列设置的集合...

跟老齐学Python之总结参数的传递

就前面所讲,函数的基本内容已经完毕。但是,函数还有很多值得不断玩味的细节。这里进行阐述。 参数的传递 python中函数的参数通过赋值的方式来传递引用对象。下面总结通过总结常见的函数参数...