def one(seq, N):
    from heapq import heapreplace

    L = [-1] * N
    for x in seq:
        if x > L[0]:
            heapreplace(L, x)

    L.sort()
    return L

def two(seq, N):
    L = []
    push = L.append
    twoN = 2*N
    for x in seq:
        push(x)
        if len(L) > twoN:
            L.sort()
            del L[:-N]

    L.sort()
    del L[:-N]
    return L

def timeit(seq, N):
    from time import clock as now

    s = now()
    r1 = one(seq, N)
    t = now()
    e1 = t - s

    s = now()
    r2 = two(seq, N)
    t = now()
    e2 = t - s

    print len(seq), N, e1, e2
    assert r1 == r2

def tryone(M, N):
    from random import random
    seq = [random() for dummy in xrange(M)]
    timeit(seq, N)

for i in range(10):
    tryone(1000000, 1000)