Python, heapq, как эффективно изменить минимальный элемент в heapq?

Question

Я использую Heapq в Python 3.7
У меня есть два вопроса о 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

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, Они являются внутренними для реализации Python heapq,

Я проверял это с Python 3.2.3