Peeking in a heap in python
PythonHeapPeekPython Problem Overview
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?
Python Solutions
Solution 1 - Python
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.)
Solution 2 - Python
If you're using Python 2.4 or newer, you can also use heapq.nsmallest().