Obtain x'th largest item in a dictionary

Question

I am looking to obtain the x'th largest item in a dictionary from the key's corresponding value.

For example, with the dictionary:

 y = {'a':55, 'b':33, 'c':67, 'd':12}

I want to be able to easily extract 'b' as the 3rd largest key.

Initially, when I was only after the top three occurrences, I made a copy of the dictionary, found the max value (e.g. following Getting key with maximum value in dictionary?), removed the key from the max value, and then re-ran. When looking for more than several highest values, this approach seems quite cumbersome. Is there a simple way of getting the corresponding key for the x'th largest item?

Answer 1

Using the heap queue algorithm:

import heapq
y = {'a':55, 'b':33, 'c':67, 'd':12}
print heapq.nlargest(n=3, iterable=y, key=y.get)[-1]
# b

This will be better performing for large dictionaries than sorting the entire dict each time. Specifically, with a dictionary of n elements where you're looking for the k largest ones, this runs in O(n log k) instead of O(n log n).

Also note that this gives you all three largest values in order as a list, simply remove the [-1]:

print heapq.nlargest(n=3, iterable=y, key=y.get)
# ['c', 'a', 'b']