from heapq import heappop, heapify, heapreplace, nlargest
from itertools import islice


def klargest_fullheap(iterable, k):
    heap = [-s for s in iterable]
    heapify(heap)
    return [-heappop(heap) for _ in range(k)]


def klargest_smallheap(iterable, k):
    heap = list(islice(iterable, k))
    heapify(heap)
    for s in iterable:
        if s > heap[0]:
            heapreplace(heap, s)
    return [heappop(heap) for _ in range(k)]


def klargest_heapq(iterable, k):
    return nlargest(k, iterable)


if __name__ == "__main__":
    from random import randrange
    from time import clock

    n = 6
    for k_exp in range(n+1):
        k = 10**k_exp
        print("k=", k)
        print("n=", 10**n)
        for method in (klargest_smallheap, klargest_fullheap,
                        klargest_heapq):
            example = (randrange(1, 1000000000) for _ in range(10**n))
            t0 = clock()
            method(example, k)
            print("{:20s} {:6.3f}".format(method.__name__, clock() - t0))