If I have a heapq which contains some elements like:
import heapq
class Element(object):
def __init__(self, name, val):
self.name = name
self.val = val
if __name__ == "__main__":
heap = []
e1 = Element('A', 1)
e2 = Element('B', 65)
e3 = Element('C', 53)
e4 = Element('D', 67)
...
heapq.heappush(heap, e1)
heapq.heappush(heap, e2)
heapq.heappush(heap, e3)
heapq.heappush(heap, e4)
...
#IF I want to take elements from the heap and print them I will call:
while heap:
new_e = heapq.heappop(heap)
print new_e.name + ' ' + str(new_e.val)
Suppose I have 50 elements on the heap. And I want to change the value of element e3 from val = 53 to val = 0. So this is NOT the top element of the heap. I also don't want to remove other elements from the heap. How can I make such update?
This is an old question, but in case someone sees this in the future and is looking for answers...
The new implementation of heapq for Python3 includes some helpful notes on how to update heap elements, essentially using it as a priority queue. https://docs.python.org/3.5/library/heapq.html#priority-queue-implementation-notes Essentially, you can make a heap of tuples, and Python will evaluate the priority based on sequential comparisons of the tuples. Since a heap in Python is basically just a standard list with the heapq interface used on top, the docs recommend possibly having an additional dictionary which maps your heap values to the index in your heap (list).
So for your original question:
Suppose I have 50 elements on the heap. And I want to change the value of element e3 from val = 53 to val = 0. So this is NOT the top element of the heap. I also don't want to remove other elements from the heap. How can I make such update?
The basic steps for updating elements in the heap following the above logic would be:
Edit: Here's a similar question with more answers: How to update elements within a heap? (priority queue)