We help IT Professionals succeed at work.

update heap ?

zizi21
zizi21 asked
on
i have a heap where i would be updating the values in the heap. Is there a function to update the heap. I have searched the net and found none..thanks.



Comment
Watch Question

Top Expert 2009

Commented:
What kind of heap are you talking about ?

Are you using your own code ? Or code you got from somewhere ? Either way, it would be useful for you to show us.

Author

Commented:
i am using the code that i got somewhere...to heapify.....

in the heap data structure, you could heapify to get the min or max but the problem is there are instances that requires the elements to be updated without popping them out.
ozo
Most Valuable Expert 2014
Top Expert 2015

Commented:
what do you mean?
http://www.itl.nist.gov/div897/sqg/dads/HTML/heap.html

If you want to do a decrease-key operation in a Fibonacci Heap
http://www.inf.ufsc.br/~kira/cormen/DDU0120.html
Top Expert 2009

Commented:
So, what you're looking for, is an _algorithm_ to modify a value in a heap ?

Well, the problem is that the heap property needs to be satisfied after every operation on the heap. Modifying a value will in general violate the heap property (unless by chance it doesn't). The most straightforward way, is to remove the old value from the heap, and add the new value.

Alternatively, you could only allow updates that don't violate the heap property.


Or maybe you were indeed referring to the increase key and decrease key heap operations like ozo suspects ?

Author

Commented:
i want to update the prorities(increase or decrease) in the heap without deleting the elements...

Author

Commented:
but at every round, i would be updating the priorities and i would take the maximum one..
ozo
Most Valuable Expert 2014
Top Expert 2015

Commented:
One way to do an update could be a delete then an insert.

Author

Commented:
yes, but the problem is that the update can be at any part in the heap. because that, i am holding a different data structure to keep track on which position the element is currently in the heap..

Author

Commented:
fibonanci heap

Especially desirable when the number of calls to Extract-Min & Delete is small (note that all other operations run in O(1)
This arises in many applications. Some graph problems, like minimum spanning tree and single-source-shortest-path problems call decrease-key much more often than other operations

Top Expert 2009
Commented:
>> but at every round, i would be updating the priorities and i would take the maximum one..

So, a priority queue with updatable priorities.


>> i want to update the prorities(increase or decrease) in the heap without deleting the elements...

You would still have to re-arrange the heap so the heap property is not violated. As I said earlier : the most straightforward way of doing that, is by removing the old, and adding the new.


>> yes, but the problem is that the update can be at any part in the heap

Why is that a problem ?

Author

Commented:
i misunderstood it..sorry.