查找最大的N個元素——堆數據結構

給出序列，求出TopK大的元素，使用小頂堆，heapq模塊實現

使用heappush()時，從數據源增加新元素時會保持元素的堆順序。
在一個操作中刪除現有元素並替換為新值，可以使用heapreplace()

import heapq

class BtmkHeap(object):
    def __init__(self, k):
        self.k = k
        self.data = []

    def Push(self, elem):
        # Reverse elem to convert to max-heap
        num1 = elem[0]
        num1 = -num1
        num2 = elem[1]
        # Using heap algorighem
        if len(self.data) < self.k:
            heapq.heappush(self.data, (num1,num2))
        else:
            topk_small = self.data[0][0]
            if elem[0] > topk_small:
                heapq.heapreplace(self.data,(num1,num2))

    def BtmK(self):
        return sorted([(-x[0],x[1]) for x in self.data])
    

if __name__ == '__main__':
    a = (100,1)
    b = (200,2)
    c = (300,3)
    d = (400,4)
    e = (50,5)
    btm = BtmkHeap(3)
    btm.Push(a)
    btm.Push(b)
    btm.Push(c)
    btm.Push(e)
    btm.Push((23,1))
    print(btm.BtmK())



結果[(23, 1), (50, 5), (100, 1)]