Finding Nth item of unsorted list without sorting the list

by

A heap is the best data structure for this operation and Python has an excellent built-in library to do just this, called heapq.

import heapq

def nth_largest(n, iter):
    return heapq.nlargest(n, iter)[-1]

Example Usage:

>>> import random
>>> iter = [random.randint(0,1000) for i in range(100)]
>>> n = 10
>>> nth_largest(n, iter)
920

Confirm result by sorting:

>>> list(sorted(iter))[-10]
920

More Related Contents:

  1. Sorting arrays in NumPy by column
  2. Sort multidimensional array based on 2nd element of the subarray
  3. How can I reorder a list? [closed]
  4. Find elements of array one nearest to elements of array two
  5. Sort invariant for numpy.argsort with multiple dimensions
  6. Efficiently sorting a numpy array in descending order?
  7. How to sort multidimensional array by column?
  8. Sorting a python array/recarray by column
  9. argsort for a multidimensional ndarray
  10. Is there a NumPy function to return the first index of something in an array?
  11. Understanding NumPy’s einsum
  12. Intuition and idea behind reshaping 4D array to 2D array in NumPy
  13. Computing the correlation coefficient between two multi-dimensional arrays
  14. pandas groupby sort within groups
  15. Removing nan values from an array
  16. Why is numpy’s einsum faster than numpy’s built in functions?
  17. sort csv by column
  18. Sorting text file by using Python
  19. Parameters to numpy’s fromfunction
  20. List to array conversion to use ravel() function
  21. Fastest save and load options for a numpy array
  22. NumPy array/matrix of mixed types
  23. How do I sort a list of objects based on an attribute of the objects?
  24. Right way to initialize an OrderedDict using its constructor such that it retains order of initial data?
  25. Sorting by absolute value without changing the data
  26. How can I slice each element of a numpy array of strings?
  27. Python 3: I am trying to find find all green pixels in an image by traversing all pixels using an np.array, but can’t get around index error
  28. Scrape Dynamic contents created by Javascript using Python
  29. Add single element to array in numpy
  30. Split a list of tuples into sub-lists of the same tuple field [duplicate]

Leave a Comment