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?

Solution

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)

Comments

[Ziva]

You missunderstand my question. I made an edit to better explain my problem and also I tried to show how I print information about elements. The code is running well.

[rocky]

With respect to "Call heapq.heapify(heap) which runs in O(N).": rebalancing should only take O(log n) or the max depth of the tree and the process is sort of like your suggestion for swapping parent/child positions. However the "update the value by +/-1" is misleading if not wrong in some cases. In particular it is wrong if priority values don't have to be unique, or if priority values are things other than ints, like floats.

[qwr]

But how do you keep the dictionary that maps elements to their index in sync while using the heap?