CODEWITHSUNDEEP
pythonpython-2.7queueheappriority-queue
Ziva
Ziva

Reputation: 3501

Python: Update value of element in heapq

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?

Upvotes: 21

Views: 29470

Answers (3)

qwr
qwr

Reputation: 10920

After identifying the index of your desired element you can call heapify on the whole heap to restore the heap. Identifying the index is the hard part since you need to keep track of where each element lives in the heap after every heap operation, and I think the easiest way to do that would just be a custom implementation of heaps.

import heapq
h = [[1, "A"], [65, "B"], [53, "C"], [67, "D"]]
heapq.heapify(h)
# assume you know index of element C is 2
h[2][0] = 0
heapq.heapify(h)

Interestingly, CPython's heapq implementation has internal methods _siftup and _siftdown. Using _siftup should be faster in practice but not in time complexity than calling heapify on the whole heap, since heapify will call _siftup n/2 times but only log(n) elements should actually get swapped.

Upvotes: 1

Joyce Lee
Joyce Lee

Reputation: 386

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)

Upvotes: 10

warship
warship

Reputation: 3024

It is difficult to run your code because there is no output. However, I tried a few things:

In the heapq module, heap[0] is always designated the smallest item. In your case, 1 is the smallest item. Therefore, changing this value from 1 to 5 should theoretically be easy. I tried heapq.heappop(heap) which should return the smallest value. Thus, as you said in your question, "I want to update val of element I don't know which in turn it is", this method gets you the smallest value automatically (I assume from your question that you want to substitute the 1 since it's the smallest value, as it is coupled with the name First) However, when I try to run your code myself I received <__main__.Element object at 0x103c15dd0> so you should try to fix your code so that you can print output, same thing goes for print heap[0], same error type. Then, once you are no longer receiving this kind of error, at the end of your code block try:

s = heapq.heappop(heap)

print heapq.heapreplace(5, s)

Using this approach, I get the following error: TypeError: heap argument must be a list Therefore, if you can figure out how to convert s into a list, then this should work. Perhaps someone can edit my answer to add this code.

Hope this helps.

SELF-EDIT:

Add this to the end of your code block, the [] turn it into a list, which is what heapq wants as input.

s = heapq.heappop(heap)

print heapq.heapreplace([5], [s])

This returns the value 5 in the output.

Going back to the output issue, if you specify what you want you want the output to look like, I can try to help you more.

Upvotes: 0

Related Questions