Heap

时间复杂度

• push：最坏 O(log n)，平均 O(1)
• pop：O(log n)

找前 n 大的数（top K）

• 先 push n 个元素到小根堆中（找前 n 小则用大跟堆）
• 对剩下的元素，和堆顶比较，若更大则替换堆顶

时间复杂度 O(n logk)。

def topk(xs: list[int], k: int):
    heap = []
    for x in xs:
        if len(heap) >= k:
            if x > heap[0]:
                heapq.heapreplace(heap, x)
        else:
            heapq.heappush(heap, x)
    return heap