Menu
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?
948
To access the smallest item without popping it, use heap[0]. So the item at the top will be the smallest one.
This module provides an implementation of the heap queue algorithm, also known as the priority queue algorithm. Heaps are binary trees for which every parent node has a value less than or equal to any of its children.
The heapq module of python implements the heap queue algorithm. It uses the min heap where the key of the parent is less than or equal to those of its children.
Yes, you can make this assumption, because it is stated in the documentation:
Heaps are arrays for which
heap[k] <= heap[2*k+1]andheap[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 thatheap[0]is always its smallest element.
(And that's probably the reason there is no peek function: there is no need for it.)
160
If you're using Python 2.4 or newer, you can also use heapq.nsmallest().
32
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
