What is time complexity of update in binary heap?

Question

For a binary heap we have O(log(n)) for insert, O(log(n)) for delete min and heap construction can be done in O(n).

In the context of using a binary heap in Djikstra, my exam paper involved an "update" in the heap where the priority of a vertex is changed.

I assumed that the time complexity of this update would be O(n) since it seemed to me that locating the vertex in the heap would require something in the order of a linear search, followed by an upheap or downheap. This would be O(n + log(n)) which is simply O(n).

Unfortunately I think this lead me to the wrong answer.

So, what is the actual time complexity of a priority update in a binary heap?

Answer 1

The key to resolving your problem is to return a special object on the insertion of a element. When you move the real object in the heap, you update the position in this object.

To call decrease-priority you pass this object so you can go right to the position in the heap and bubble up the element if necessary.

In this way it's O(log(n)). In fact finding the element is O(1) and restoring the heap property is O(log(n)).

P.s. You should check whether the new priority actually decreases.

Answer 2

I'm going to disagree a bit with Scara95. With out context of your answer this seems like whether or not your answer is wrong could possibly be a matter of pedantry. Technically, yes, its not O(N) + O(log(N)) because it is possible to find the location of elements in constant time. However, this requires an entirely different data-structure to go along with your binary heap. You have to map inserted elements to a hash table, such that when you insert elements into the priority you also insert a new entry into the hashtable, a unique hash of the element you just inserted, with the location as the value.

To update, you query the hashtable with the ID of the element in the priority queue you want to update, and grab the hashtable elements value to find out where to update the priority queue element, where you percolate up/heapify up / down

But at this point, you no longer have just a binary heap, you have a binary heap and a hash-table, arguably a new data structure as the actual functions to update the heap can't be separated from the two data-structures. You can actually implement binary heaps where the update complexity can't get better than O(N) given that you simply don't include a hashtable. Often you'll even find papers on new algorithms/data-structures are actually the same data structures but with new components often other datastructures mixed in the same way the hash-table would have to be, so this makes this whole exercise extra confusing.

Bottom line is that if the question asked you about what the best possible update complexity would be for a binary heap, your answer was wrong, no questions asked, but if the question was more specific in terms of what you guys talked about in class, talking about a binary heap formed in a specific way, things get a lot more complicated.