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

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

在Django同1个页面中的多表单处理详解
快速上手Django实现项目近期公司在做1个海淘的项目,APP为pylot。由于时间比较赶,加上隔壁那哥们不在,只能自己挑大梁了。结果,当项目做出来之后,被领导

Python下的Softmax回归函数的实现方法(推荐)
Softmax回归函数是用于将分类结果归一化。但它不同于一般的按照比例归一化的方法，它通过对数变换来进行归一化，这样实现了较大的值在归一化过程

详解python之简单主机批量管理工具
今天做了一个很简单的小项目，感受到了paramiko模块的强大，也深感自己Linux的功力不行~~一、需求二、简单需求分析及流程图需求很少，我就简单地说