Do I need to heapify after initializing a heap in Python3

user_11912396 0
Viewed 1221

When a heap is created to dynamically track a min value, after initialising an empty heap, do I actually need to call heapq.heapify(heap)? Or rather hq.heappop() and hp.heappush() will automatically do the job.. Thanks for the help!

import heapq as hp
heap = []
hp.heapify(heap) # is this line redundant?
for val in range(1, 100):
    hp.heappush(heap, val)
    print(heap[0])
min-heap heap python-3.x
1 Answers

Yep, in your case it's redundant. From the official doc here:

heapq.heappush(heap, item)

Push the value item onto the heap, maintaining the heap invariant.

heapq.heapify(x)

Transform list x into a heap, in-place, in linear time.

As you can see from the description of the heapify method, it's used for conversion of an existing list to a heap structure.

However, if you would like to keep the heap property of your data structure when adding new elements, then heappush is a way to go.

import heapq as hp
heap = []
for val in range(1, 100):
    hp.heappush(heap, val)
    print(heap[0])

However, if you would like to convert an existing array / list to a heap, then use the heapify method:

import heapq as hp
heap = []
for val in range(1, 100):
    heap.append(val)
hp.heapify(heap)
print(heap[0])
user_10553950
Related