堆(heap)：从海量数据中寻找最大的k个值

                                     从海量数据中寻找最大的k个值

 

1、目的：获取大量元素 topk 大个元素，固定内存

2、思路：

    (1) 先放入元素前 k 个建立一个最小堆；

    (2) 迭代剩余元素：

        a、如果当前元素小于堆顶元素，跳过该元素（肯定不是前 k 大）；

        b、否则替换堆顶元素为当前元素，并重新调整。

3、代码示例：

import heapq


class TopK():
    """
    获取大量元素 topk 大个元素，固定内存
    思路：
        1、先放入元素前 k 个建立一个最小堆；
        2、迭代剩余元素：
            如果当前元素小于堆顶元素，跳过该元素（肯定不是前 k 大）
            否则替换堆顶元素为当前元素，并重新调整堆
    """

    def __init__(self, iterable, k):
        self.minheap = []
        self.capacity = k
        self.iterable = iterable

    def push(self, value):
        if len(self.minheap) >= self.capacity:
            min_value = self.minheap[0]
            if value > min_value:
                # 返回并且pop堆顶最小值，推入新的 value 值并调整堆
                heapq.heapreplace(self.minheap, value)
        else:
            # 前 k 个元素直接放入 minheap
            heapq.heappush(self.minheap, value)

    def get_topk(self):
        for value in self.iterable:
            self.push(value)
        return self.minheap


if __name__ == "__main__":
    import random
    data_list = list(range(1000))
    random.shuffle(data_list)
    top_k = TopK(data_list, 10)
    print(top_k.get_topk())

4、运行结果：