I have no idea how to solve following problem efficiently without using _siftup
or _siftdown
:
How to restore the heap invariant, when one element is out-of-order?
In other words, update old_value
in heap
to new_value
, and keep heap
working. you can assume there is only one old_value
in heap. The fucntion definition is like:
def update_value_in_heap(heap, old_value, new_value):
Here is _siftup or _siftdown version:
>>> from heapq import _siftup, _siftdown, heapify, heappop
>>> data = [10, 5, 18, 2, 37, 3, 8, 7, 19, 1]
>>> heapify(data)
>>> old, new = 8, 22 # increase the 8 to 22
>>> i = data.index(old)
>>> data[i] = new
>>> _siftup(data, i)
>>> [heappop(data) for i in range(len(data))]
[1, 2, 3, 5, 7, 10, 18, 19, 22, 37]
>>> data = [10, 5, 18, 2, 37, 3, 8, 7, 19, 1]
>>> heapify(data)
>>> old, new = 8, 4 # decrease the 8 to 4
>>> i = data.index(old)
>>> data[i] = new
>>> _siftdown(data, 0, i)
>>> [heappop(data) for i in range(len(data))]
[1, 2, 3, 4, 5, 7, 10, 18, 19, 37]
it costs O(n) to index and O(logn) to update. heapify
is another solution, but less efficient than _siftup
or _siftdown
.
But _siftup
and _siftdown
are protected member in heapq, so they are not recommended to access from outside.
So is there a better and more efficient way to solve this problem? Best practice for this situation?
Thanks for reading, I really appreciate it to help me out. : )
already refer to heapq python - how to modify values for which heap is sorted, but no answer to my problem.
from how to avoid using _siftup or _siftdown in heapq
No comments:
Post a Comment