6

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?

  • 1
    If you're referring to decrease-key, it is O(log n) according to en.wikipedia.org/wiki/…. Apparently it assumes you already know where the vertex is located, so no need for the linear search. – Robert Harvey Nov 16 '15 at 7:09
  • 2
    If you use a heap for the priority queue in Djikstra, then I don't see how you could know where the vertex is in the heap. Surely a linear search is required. – Brendan Hill Nov 16 '15 at 7:43
  • Maybe the linear search is just not considered part of the decrease-key operation. When you delete a node out of a binary tree, you don't count "finding the node" in the complexity; that's already a separate operation having its own complexity assignment. All complexities for "delete" operations assume that you already have knowledge of the node that you want to delete. – Robert Harvey Nov 16 '15 at 7:45
6

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.

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.