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

Question

I am using heapq in python 3.7
I have two questions about heapq:

1. I don't know how to keep the heap invariant efficiently if I just want to modify the min element.
   And here is my implementation. (It is quite slow)

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

2. what do these two methods _siftdown() and _siftup() use for? And what is the difference between them? How to use these two methods to maintain the heap invariant?

Finally, I implement a code using _siftdown() (But I am Still confused about these two methods and do not ensure that whether my code is correct.)

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)

The output is:

10000
0.09700560569763184
10000
7.193411350250244

Answer 1

Use heapq.heapreplace. The smallest item is always at q[0] so modify it if needed and then call:

heapq.heapreplace(q, q[0])

I ran your timing and rewrote it for speed:

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)

Produces:

10000
0.006845951080322266
10000
0.06091189384460449

It is faster to create a list and then call heapify on it then to use heappush.

heapq.heapreplace is faster than heapq._siftup as heapreplace uses the C module for heapq where as _siftup is in Python. _siftup and _siftdown only appear in heapq.py not in the _heapq module

Do not call either _siftup or _siftdown. They are internal to the Python implementation of heapq.

I tested this with Python 3.2.3