evernote contest

top_four.py

# coding: utf-8

'''
Given an unordered list of N elements, write a function to find the top four elements of the given list. Make sure your function runs in linear time O(N).
 
Input format :
 
First line of input contains N , number of elements in list.
Next N line , each contains a element.
 
Output format :
 
Print the top four elements of list.
 
Sample input :
 
8
6930886
-1692777
4636915
7747793
-4238335
9885386
9760492
6516649
 
Sample ouput :
 
9885386
9760492
7747793
6930886
 
Constraint :
 
N < 1000000.
all numbers will fit  in 32-bit integer.
'''


import heapq


def find_top_4(elements):
    if len(elements) < 5:
        return sorted(elements, reverse=True)

    heap = []
    heapq.heapify(heap)
    heap_min = min(heap)
    for e in elements:
        if e <= heap_min:
            continue
        heapq.heappushpop(heap, e)
        heap_min = min(heap)

    return sorted(heap, reverse=True)


def main():
    n = int(raw_input())
    l = []
    for i in xrange(n):
        l.append(int(raw_input()))
    for e in find_top_4(l):
        print e


if __name__ == "__main__":
    main()

nice work, 2 small bugs:
replace line :
heap = []
with :
heap = elements[:4]

and replace line:
for e in elements:
with
for e in elements[4:]: