Peeking in a heap in python

python heap peek
Thomas picture Thomas · Nov 17, 2009 · Viewed 19k times · Source

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?

Answer

Stephan202 picture Stephan202 · Nov 17, 2009

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

Related questions

What do I use for a max-heap implementation in Python?

Python includes the heapq module for min-heaps, but I need a max heap. What should I use for a max-heap implementation in Python?

Read More
What is Python's heapq module?

I tried "heapq" and arrived at the conclusion that my expectations differ from what I see on the screen. I need somebody to explain how it works and where it can be useful. From the book Python Module of the …

Read More
How to make heapq evaluate the heap off of a specific attribute?

I wish to hold a heap of objects, not just numbers. They will have an integer attribute in them that the heap can sort by. The easiest way to use heaps in python is heapq, but how do I tell …

Read More