Python heapq 詳解
Python有一個內(nèi)置的模塊，heapq標準的封裝了最小堆的算法實現(xiàn)。下面看兩個不錯的應(yīng)用。
小頂堆（求TopK大）
話說需求是這樣的： 定長的序列，求出TopK大的數(shù)據(jù)。
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小的元素，即使用大頂堆。
算法實現(xiàn)的核心思路是：將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])
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
新聞熱點
疑難解答
圖片精選
