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个性签名设计实现代码

本文实例为大家分享了python个性签名设计的具体代码,供大家参考,具体内容如下 参考博客:Python GUI Tkinter简单实现个性签名设计 参考博客:python3爬虫之设计签...

关于pandas的离散化,面元划分详解

pd.cut pandas.cut(x, bins, right=True, labels=None, retbins=False, precision=3, include_low...

python读写json文件的简单实现

python读写json文件的简单实现

JSON(JavaScript Object Notation) 是一种轻量级的数据交换格式。它基于ECMAScript的一个子集。 JSON采用完全独立于语言的文本格式,但是也使用了类...

flask 实现上传图片并缩放作为头像的例子

个人开发的 flask 论坛进入尾声,还剩最后一个上传图片更换头像功能,搞了一整天,最后终于解决了所有问题,现在记录下解决方案。 1. 上传文件 分析一下更换头像功能,我们需要做哪些事,...

Python3.6安装及引入Requests库的实现方法

Python3.6安装及引入Requests库的实现方法

本博客可能没有那么规范,环境之类的配置。只是让你直接开始编程写python。 至于各种配置网络上有多种方法。 本文仅代表我的观点的一种方法。 电脑环境:win10 64位 第一步:下载p...