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
 
    for k in (10, 20, 40, 80, 160, 320, 640, 1280):
        n = 5
        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))

ZnJvbSBoZWFwcSBpbXBvcnQgaGVhcHBvcCwgaGVhcGlmeSwgaGVhcHJlcGxhY2UsIG5sYXJnZXN0CmZyb20gaXRlcnRvb2xzIGltcG9ydCBpc2xpY2UKCgpkZWYga2xhcmdlc3RfZnVsbGhlYXAoaXRlcmFibGUsIGspOgogICAgaGVhcCA9IFstcyBmb3IgcyBpbiBpdGVyYWJsZV0KICAgIGhlYXBpZnkoaGVhcCkKICAgIHJldHVybiBbLWhlYXBwb3AoaGVhcCkgZm9yIF8gaW4gcmFuZ2UoayldCgoKZGVmIGtsYXJnZXN0X3NtYWxsaGVhcChpdGVyYWJsZSwgayk6CiAgICBoZWFwID0gbGlzdChpc2xpY2UoaXRlcmFibGUsIGspKQogICAgaGVhcGlmeShoZWFwKQogICAgZm9yIHMgaW4gaXRlcmFibGU6CiAgICAgICAgaWYgcyA+IGhlYXBbMF06CiAgICAgICAgICAgIGhlYXByZXBsYWNlKGhlYXAsIHMpCiAgICByZXR1cm4gW2hlYXBwb3AoaGVhcCkgZm9yIF8gaW4gcmFuZ2UoayldCgoKZGVmIGtsYXJnZXN0X2hlYXBxKGl0ZXJhYmxlLCBrKToKICAgIHJldHVybiBubGFyZ2VzdChrLCBpdGVyYWJsZSkKCgppZiBfX25hbWVfXyA9PSAiX19tYWluX18iOgogICAgZnJvbSByYW5kb20gaW1wb3J0IHJhbmRyYW5nZQogICAgZnJvbSB0aW1lIGltcG9ydCBjbG9jawoKICAgIGZvciBrIGluICgxMCwgMjAsIDQwLCA4MCwgMTYwLCAzMjAsIDY0MCwgMTI4MCk6CiAgICAgICAgbiA9IDUKICAgICAgICBwcmludCgiaz0iLCBrKQogICAgICAgIHByaW50KCJuPSIsIDEwKipuKQogICAgICAgIGZvciBtZXRob2QgaW4gKGtsYXJnZXN0X3NtYWxsaGVhcCwga2xhcmdlc3RfZnVsbGhlYXAsCiAgICAgICAgICAgICAgICAgICAgICAgIGtsYXJnZXN0X2hlYXBxKToKICAgICAgICAgICAgZXhhbXBsZSA9IChyYW5kcmFuZ2UoMSwgMTAwMDAwMDAwMCkgZm9yIF8gaW4gcmFuZ2UoMTAqKm4pKQogICAgICAgICAgICB0MCA9IGNsb2NrKCkKICAgICAgICAgICAgbWV0aG9kKGV4YW1wbGUsIGspCiAgICAgICAgICAgIHByaW50KCJ7OjIwc30gezo2LjNmfSIuZm9ybWF0KG1ldGhvZC5fX25hbWVfXywgY2xvY2soKSAtIHQwKSk=