maxHeap python 在弹出元素后转换为最小堆

Question

试图理解 python 中的最大堆。一旦我弹出元素，元素就会被排列为最小堆。

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)

一旦我在 python 中弹出一个元素，最大堆是否会转换回最小堆？

Answer 1

没有特殊的“属性”将堆标记为最大堆。

默认heapq是最小堆，所有常用操作（如heappop）都意味着最小堆。

所以你必须再次使用带下划线的函数版本：

heapq._heappop_max(a) 


[9, 4, 1, 3, 2]
[4, 3, 1, 2]
[3, 2, 1]

PS 老技巧，也许在*_max函数出现之前：只需对初始列表中的数字和压入/弹出的值求负即可。