Python, heapq, 如何高效修改heapq中的最小元素？

Question

我在 python 3.7
中使用 heapq 我有两个关于 heapq 的问题：

如果我只是想修改最小元素，我不知道如何有效地保持堆不变。
这是我的实现。（相当慢）
```
q= [5,8,9,10]
heapq.heapify(q)
q[0] = 1200
heapq.heapify(q)
```
_siftdown()和_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 使用 C 模块 heapq 而 _siftup 在 Python 中。 _siftup 和 _siftdown 仅出现在 heapq.py 中而不出现在 _heapq 模块中

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

我用 Python 3.2.3

测试了这个

Python, heapq, 如何高效修改heapq中的最小元素？

Python, heapq, How to efficiently modify the minimum element in heapq?

python

data-structures

heapq