Peeking in a heap in python

Question

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?

Goidelic

Yes you can use heap[0] – Vedanta

Answer 1

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.)

Adolf

The reason why I couldn't find this information was probably that I've misspelled peek. Great! – Goidelic

Though spelling it right would probably have helped you, I observe that curiously that word does not occur in the documentation anyway. – Adolf

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 – Mopes

@Mopes that's not true, and it doesn't need to be true. You can try out with a simple example yourself. – Columniation

+1 As you can see the binary tree, the nodes on same level are not sorted in order they are only lesser or greater than the parent – Murmurous

Answer 2

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

Gatto

Is "n" 1 in this case? – Realty

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]. – Gook

Answer 3

heapq.heappop(heap) Pop and return the smallest item from the heap, maintaining the heap invariant. If the heap is empty, IndexError is raised. To access the smallest item without popping it, use heap[0].

Python3 documentation clearly states that you can use heap[0] to peek the smallest element without popping.

Note: You can use negative notation if you want to maintain the max heap.

Coagulate