tags:

views:

241

answers:

1

Hi all.

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?

+8  A: 

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
The reason why I couldn't find this information was probably that I've misspelled peek. Great!
Thomas
Though spelling it right would *probably* have helped you, I observe that curiously that word does not occur in the documentation anyway.
Stephan202