弹出元素后最大堆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

没有特殊的“属性”将堆标记为max-heap。

heapq 中的默认值是 min-heap，所有常用操作（如 heappop）都表示 min-heap。

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

heapq._heappop_max(a) 


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

P.S。老把戏，也许在 *_max 函数出现之前：只需取反初始列表中的数字和 pushed/popped 值。

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

maxHeap python converts to min heap after poping element

python

algorithm

heapq