Trying to understand the max heap in python. Once I pop the element the elements are arranged as min heap.
import heapq
a=[3,2,1,4,9]
heapq._heapify_max(a) # This createa a binary tree with max val at the root
print(a) # This should be [9,4,3,2,1]
heapq.heappop(a) # when poped state of a will be [4,....]
print(a) # But a is [1,4,2,3] -- Why?
heapq.heappop(a)
print(a)
b=[3,2,1,4,9]
heapq.heapify(b)
print(b) # [1,2,3,4,9]
heapq.heappop(b) # pops 1 out
print(b) # [2,4,3,9]
heapq.heappop(b) # pops 2 out
print(b) # [3,4,9]
To keep the state of max heap I am currently using maxheap inside a while loop
while count_heap or q:
heapq._heapify_max(count_heap)
Does max heap converts back to min heap once I pop an element in python?
CodePudding user response:
There is no special "property" to mark heap as max-heap.
Default in heapq
is min-heap, all usual operations (like heappop
) imply min-heap.
So you have to use underscored function versions again:
heapq._heappop_max(a)
[9, 4, 1, 3, 2]
[4, 3, 1, 2]
[3, 2, 1]
P.S. Old trick, perhaps before *_max
functions appearance: just negate numbers in the initial list and pushed/popped values.