Python heapq 詳解

Python有一個內置的模塊，heapq標準的封裝了最小堆的算法實現。下面看兩個不錯的應用。

小頂堆（求TopK大）

話說需求是這樣的： 定長的序列，求出TopK大的數據。

import heapqimport randomclass 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])

 感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！