import time, random, heapq
 
class Timer:
    def __init__(self, description):
        self.description = description
 
    def __enter__(self):
        self.start = time.perf_counter()
        return self
 
    def __exit__(self, *args):
        end = time.perf_counter()
        print(f"The time for {self.description} took: {end - self.start}.")
 
 
def f3(x,k): # O(N) Time | O(N) Storage
    y = []
    idx=0
    while idx<k:
        curr_min = min(x)
        x.remove(curr_min)
        y.append(curr_min)
        idx += 1
    return y
 
 
def f_heap(x, k): # O(nlogn)
    heapq.heapify(x)
    return [heapq.heappop(x) for _ in range(k)]
 
 
 
N=1000000
x = [random.randint(0,N) for i in range(N)]
 
TRIALS = 1
 
with Timer('f3') as t:
    for _ in range(TRIALS):
        y = f3(x.copy(), 10)
print(y)
 
print()
 
with Timer('f_heap') as t:
    for _ in range(TRIALS):
        y = f_heap(x.copy(), 10)
print(y)

aW1wb3J0IHRpbWUsIHJhbmRvbSwgaGVhcHEKCmNsYXNzIFRpbWVyOgogICAgZGVmIF9faW5pdF9fKHNlbGYsIGRlc2NyaXB0aW9uKToKICAgICAgICBzZWxmLmRlc2NyaXB0aW9uID0gZGVzY3JpcHRpb24KCiAgICBkZWYgX19lbnRlcl9fKHNlbGYpOgogICAgICAgIHNlbGYuc3RhcnQgPSB0aW1lLnBlcmZfY291bnRlcigpCiAgICAgICAgcmV0dXJuIHNlbGYKCiAgICBkZWYgX19leGl0X18oc2VsZiwgKmFyZ3MpOgogICAgICAgIGVuZCA9IHRpbWUucGVyZl9jb3VudGVyKCkKICAgICAgICBwcmludChmIlRoZSB0aW1lIGZvciB7c2VsZi5kZXNjcmlwdGlvbn0gdG9vazoge2VuZCAtIHNlbGYuc3RhcnR9LiIpCgoKZGVmIGYzKHgsayk6ICMgTyhOKSBUaW1lIHwgTyhOKSBTdG9yYWdlCiAgICB5ID0gW10KICAgIGlkeD0wCiAgICB3aGlsZSBpZHg8azoKICAgICAgICBjdXJyX21pbiA9IG1pbih4KQogICAgICAgIHgucmVtb3ZlKGN1cnJfbWluKQogICAgICAgIHkuYXBwZW5kKGN1cnJfbWluKQogICAgICAgIGlkeCArPSAxCiAgICByZXR1cm4geQoKCmRlZiBmX2hlYXAoeCwgayk6ICMgTyhubG9nbikKICAgIGhlYXBxLmhlYXBpZnkoeCkKICAgIHJldHVybiBbaGVhcHEuaGVhcHBvcCh4KSBmb3IgXyBpbiByYW5nZShrKV0KCgoKTj0xMDAwMDAwCnggPSBbcmFuZG9tLnJhbmRpbnQoMCxOKSBmb3IgaSBpbiByYW5nZShOKV0KClRSSUFMUyA9IDEKCndpdGggVGltZXIoJ2YzJykgYXMgdDoKICAgIGZvciBfIGluIHJhbmdlKFRSSUFMUyk6CiAgICAgICAgeSA9IGYzKHguY29weSgpLCAxMCkKcHJpbnQoeSkKCnByaW50KCkKCndpdGggVGltZXIoJ2ZfaGVhcCcpIGFzIHQ6CiAgICBmb3IgXyBpbiByYW5nZShUUklBTFMpOgogICAgICAgIHkgPSBmX2hlYXAoeC5jb3B5KCksIDEwKQpwcmludCh5KQ==