title: n-largest elements in a sequence (need to retain duplicates)
body: <p>I need to find the n largest elements in a list of tuples. Here is an example for top 3 elements.</p>
  <pre><code># I have a list of tuples of the form (category-1, category-2, value)
  # For each category-1, ***values are already sorted descending by default***
  # The list can potentially be approximately a million elements long.
  lot = [('a', 'x1', 10), ('a', 'x2', 9), ('a', 'x3', 9), 
         ('a', 'x4',  8), ('a', 'x5', 8), ('a', 'x6', 7),
         ('b', 'x1', 10), ('b', 'x2', 9), ('b', 'x3', 8), 
         ('b', 'x4',  7), ('b', 'x5', 6), ('b', 'x6', 5)]
  
  # This is what I need. 
  # A list of tuple with top-3 largest values for each category-1
  ans = [('a', 'x1', 10), ('a', 'x2', 9), ('a', 'x3', 9), 
         ('a', 'x4', 8), ('a', 'x5', 8),
         ('b', 'x1', 10), ('b', 'x2', 9), ('b', 'x3', 8)]
  </code></pre>
  <p>I tried using <code>heapq.nlargest</code>. However it only returns the first 3 largest elements and doesn't return duplicates. For example,</p>
  <pre><code>heapq.nlargest(3, [10, 10, 10, 9, 8, 8, 7, 6])
  # returns
  [10, 10, 10]
  # I need
  [10, 10, 10, 9, 8, 8]
  </code></pre>
  <p>I can only think of a brute force approach. This is what I have and it works.</p>
  <pre><code>res, prev_t, count = [lot[0]], lot[0], 1
  for t in lot[1:]:
      if t[0] == prev_t[0]:
          count = count + 1 if t[2] != prev_t[2] else count
          if count &lt;= 3:
              res.append(t)   
      else:
          count = 1
          res.append(t)
      prev_t = t
  
  print res
  </code></pre>
  <p>Any other ideas on how I can implement this?</p>
  <p>EDIT: <code>timeit</code> results for a list of 1 million elements show that <a href="https://stackoverflow.com/questions/6669632/n-largest-elements-in-an-sequence-need-to-retain-duplicates/6670141#6670141">mhyfritz's solution</a> runs in 1/3rd the time of brute force. Didn't want to make the question too long. So added more details in <a href="https://stackoverflow.com/questions/6669632/n-largest-elements-in-an-sequence-need-to-retain-duplicates/6671383#6671383">my answer</a>.</p>