heapq._heapify_max function not working properly in python

Question

I am working on a leetcode problem 1962 in which i have used heapq._heapify_max(list) function and found it is not working properly

I tried directly popping the elements max heapq with the function heapq.heappop(list) but it gives me max element only on the first pop and returns min elements for the remaining. So i have also tried the function heapq._heappop_max(list) but this also returns me max elements only on first two times of popping and min elements for remaining time. Can someone explain me why this is happening. this is my code

class Solution:
    def minStoneSum(self, piles: List[int], k: int) -> int:
        heapq._heapify_max(piles)
        for _ in range(k):
            x = heapq._heappop_max(piles)
            print(x)
            heapq.heappush(piles, (x // 2) if (x % 2 == 0) else (x // 2 + 1))
        return sum(piles)

Answer 1

The heapq module of python implements the heap queue algorithm. It uses the min heap. when you are using heapq.heappush() will push smaller values above to the root just contradict as you wanted maximum value in root.

To perform max heap in python the general method is to store values in negative the larger the negative is correspond to the maximum value in the list..!

Code:-

import heapq
class Solution:
    def minStoneSum(self, piles: List[int], k: int) -> int:
        maxheap=[]
        for i in piles:
            maxheap.append(-i) #Storing values in negative so that heapify will give max value in form of negative
        
        heapq.heapify(maxheap)
        #print(maxheap) #To see how your maxheap looks like
        while k:
            a=-heapq.heappop(maxheap)
            a=ceil(a/2)
            heapq.heappush(maxheap,-a)  #Don't forget to store value in negative
            k-=1
        return -sum(maxheap)   #Don't forget to convert sum into positive