Retrieve the two highest item from a list containi

Question

How can retrieve the two highest item from a list containing 100,000 integers without having to sort the entire list first?

Answer 1

You iterate over the list, maintaining variables that contain the value of the highest and the second highest item encountered thus far. Each new item that is encountered will replace whichever of the two the new item is higher than (if any).

Answer 2

Without sorting the list the only way to really do it is to iterate through the whole list and save the highest two numbers. I think you'd be better off sorting the list.

Answer 3

I know this topic is old, but here is a simple solution to this problem. Tested against heapq.nlargest and this is a bit faster (no sorting needed):

Works for both positive and negative numbers.

Function below: Max time used: 0.12, max memory used: 29290496 heapq.nlargest: Max time used: 0.14, max memory used: 31088640

def two_highest_numbers(list_to_work):

    first = None
    second = None

    for number in list_to_work:
        if first is None:
            first = number
        elif number > first:
            second = first
            first = number
        else:
            if second is None:
                second = number
            elif number > second:
                second = number

return [first, second]