Python，heapq，如何有效地修改heapq中的最小元素？

Question

我在python3.7中使用heapq
我有两个关于heapq的问题：

1. 如果我只想修改min元素，我不知道如何有效地保持堆不变。
   这是我的实现。（相当慢）

   q= [5,8,9,10]
   heapq.heapify(q)
   q[0] = 1200
   heapq.heapify(q)
   

2. 这两个方法\u siftdown（）和\u siftup（）的用途是什么？它们之间有什么区别？如何使用这两种方法来保持堆不变？

最后，我使用siftdown（）实现了一个代码（但是我仍然对这两种方法感到困惑，无法确定我的代码是否正确。）

s = time.time()
q = []
for i in range(0, 10000):
    heapq.heappush(q, i)
for i in range(0, 10000):
    q[0] = 10000+i
    heapq._siftup(q,0)
print(q[0])
e2 =time.time()

print(e2-s)

s = time.time()
q = []
for i in range(0, 10000):
    heapq.heappush(q, i)
for i in range(0, 10000):
    q[0] = 10000+i
    heapq.heapify(q)
print(q[0])
e2 =time.time()

print(e2-s)

输出为：

10000
0.09700560569763184
10000
7.193411350250244

Answer 1

使用heapq.heapreplace。最小的项目总是在q[0]，因此如果需要，请修改它，然后调用：

heapq.heapreplace(q, q[0])

我运行了你的计时并重写了它以提高速度：

import time
import heapq

s = time.time()
q = list(range(0, 10000))
heapq.heapify(q)

for i in range(0, 10000):
    heapq.heapreplace(q, 10000+i)

print(q[0])
e2 = time.time()

print(e2 - s)


s = time.time()
q = list(range(0, 10000))
heapq.heapify(q)

for i in range(0, 10000):
    q[0] = 10000+i
    heapq._siftup(q, 0)

print(q[0])
e2 = time.time()

print(e2 - s)

产生：

10000
0.006845951080322266
10000
0.06091189384460449

创建一个列表，然后调用它上的heapify，然后使用heappush，速度更快。你知道吗

heapq.heapreplace比heapq._siftup快，因为heapreplace对heapq使用C模块，其中as_siftup在Python中。_siftup和_siftdown只出现在heapq.py中，而不出现在_heapq模块中

不要调用_siftup或_siftdown。它们是heapq的Python实现的内部。你知道吗

我用python3.2.3测试了这个