CODEWITHSUNDEEP
pythonheappeek
Thomas
Thomas

Reputation: 2859

Peeking in a heap in python

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?

Upvotes: 70

Views: 69402

Answers (4)

Eric Leschinski
Eric Leschinski

Reputation: 154101

Example of peeking a heapq heap in python3:

import heapq 

#define a list with items in it called li 
li = [3,5,9,1,2,3, 100, 300, 500, 5, 4, 3] 
print("li: '" + str(li) + "'") 
 
def top_3_elements(li): 
     
    #Make a new python list which contains the first three elements 
    top_three = li[0:3] 
    #heapify the list using heapq 
    heapq.heapify(top_three) 
    
    #enumerate every item from position 3 until the end 
    for item in li[3:]: 
        print("item: '" + str(item) + "'") 
        #==== heapq peek ===== 
        #If the smallest item from the heap [an order(1) operation] is less than item 
        if top_three[0] < item: 
            #then remove the smallest one 
            heapq.heappop(top_three) 
 
            #then add the item to top three 
            heapq.heappush(top_three, item) 
            print("new top_three: '" + str(top_three) + "'") 
 
print(top_3_elements(li))

which prints:

li: '[3, 5, 9, 1, 2, 3, 100, 300, 500, 5, 4, 3]' 
item: '1' 
item: '2' 
item: '3' 
item: '100' 
new top_three: '[5, 9, 100]' 
item: '300' 
new top_three: '[9, 100, 300]' 
item: '500' 
new top_three: '[100, 300, 500]' 
item: '5' 
item: '4' 
item: '3'

Runtime complexity: O(n * log k) where k is a constant '3'.

Upvotes: -1

work_in_progress
work_in_progress

Reputation: 767

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.

Upvotes: 0

DannyTree
DannyTree

Reputation: 1173

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

Upvotes: 7

Stephan202
Stephan202

Reputation: 61609

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

Upvotes: 103

Related Questions