替换元素的堆解决方案是否比弹出然后推送的解决方案更有效？

Question

我正在编写以下问题的解决方案： https://leetcode.com/problems/remove-stones-to-minimize-the-total/

我的问题只是比较两个解决方案。

我正在使用 max heap 来解决问题，我从堆中取出 max value，对其进行一些计算（它变成一个较小的数字），然后将其推送回到堆中。这是我的代码：

from math import floor
import heapq
def minStoneSum(piles, k: int) -> int:
    while k > 0:
        heapq._heapify_max(piles)
        max_pile = heapq._heappop_max(piles)
        remove_stones = floor(max_pile / 2)
        replacement = max_pile- remove_stones
        heapq.heappush(piles,replacement)
        k -= 1

    return sum(piles)

print(minStoneSum([5,4,9], 2))

虽然它通过了大部分测试，但它确实产生了 Time Out error。

我找到了另一个解决方案，我认为它与我的非常相似：

def minStoneSum(self, piles: List[int], k: int) -> int:
        
        pq = [-x for x in piles]
        heapify(pq)
        for _ in range(k): 
            heapreplace(pq,pq[0]//2)
        return -sum(pq)

但是这段代码通过了所有测试！我的效率较低是因为我正在弹出最大值，在重新插入它时进行一些计算吗？而这段代码只是简单地替换了每次迭代中的最大值？

Answer 1

heapreplace不改变堆的大小，替换值后，新值需要向下堆进行筛选，以便恢复堆属性.

_heappop_max 通过将最后一个值移动到第一个槽位来缩短堆，然后向下筛选堆中的那个值。

heappush 将在末尾添加新值并执行筛选 up。然而，这个动作真的很费力吗，因为 heappush 将假定一个最小堆组织......最常将新值移动到错误的位置。这就是为什么您需要反复对堆进行堆化...

这可能是成本最高的手术。您的代码重复调用 _heapify_max，而最佳解决方案只需堆化一次。

替换元素的堆解决方案是否比弹出然后推送的解决方案更有效？

Is a heap solution that replaces elements more efficient than one that pops then pushes?

python

heap