0

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

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

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

  2. _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
4

1 回答 1

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._siftupas在 Python中heapreplace使用 C 模块的heapqwhere as is 更快。并且只出现在不在模块中_siftup_siftup_siftdownheapq.py_heapq

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

我用 Python 3.2.3 测试了这个

于 2018-12-08T11:41:32.943 回答