Home > Enterprise >  maxHeap python converts to min heap after poping element
maxHeap python converts to min heap after poping element

Time:03-16

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.

  • Related