Python: Update value of element in heapq

Question

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?

Answer 1

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:

• Check dictionary to get the index of the element you want to update (after checking that the element is in the dictionary + corresponding heap)
• Update the value in the heap
• Call heapq.heapify(heap) which runs in O(N). Alternatively, if you know your update will update the value by +/- 1, you could potentially just swap the position of the element you're trying to update with the element above or below it.

Edit: Here's a similar question with more answers: How to update elements within a heap? (priority queue)