62

What is the official way of peeking in a python heap as created by the heapq libs? Right now I have

def heappeak(heap):
  smallest = heappop(heap)
  heappush(heap, smallest)
  return smallest

which is arguably, not very nice. Can I always assume that heap[0] is the top of the heap and use that? Or would that assume too much of the underlying implementation?

Joe
  • 41,484
  • 20
  • 104
  • 125
Thomas
  • 2,769
  • 5
  • 21
  • 21

2 Answers2

88

Yes, you can make this assumption, because it is stated in the documentation:

Heaps are arrays for which heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2] for all k, counting elements from zero. For the sake of comparison, non-existing elements are considered to be infinite. The interesting property of a heap is that heap[0] is always its smallest element.

(And that's probably the reason there is no peek function: there is no need for it.)

Stephan202
  • 59,965
  • 13
  • 127
  • 133
  • The reason why I couldn't find this information was probably that I've misspelled peek. Great! – Thomas Nov 17 '09 at 19:05
  • 6
    Though spelling it right would *probably* have helped you, I observe that curiously that word does not occur in the documentation anyway. – Stephan202 Nov 17 '09 at 19:10
  • 1
    I would take this answer one step further and say that not only is heap[0] the smallest element, but heap[1] is the second smallest element, heap[2] the third smallest, etc – BeeGee Mar 01 '21 at 14:52
  • 8
    @BeeGee that's not true, and it doesn't need to be true. You can try out with a simple example yourself. – Sнаđошƒаӽ Jul 05 '21 at 18:17
9

If you're using Python 2.4 or newer, you can also use heapq.nsmallest().

DannyTree
  • 1,137
  • 2
  • 12
  • 16
  • 3
    Is "n" 1 in this case? – WestCoastProjects Apr 22 '17 at 15:14
  • 3
    Be sure to check the complexity of `nsmallest()` you are using. In 3.8 I see e.g. "Make a single pass over the data while keeping the k most extreme values in a heap." ... not ideal for n=1, if you can just `heap[0]`. – P Marecki Apr 04 '21 at 07:28