Python heapq使用详解及实例代码

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

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