changing priority of binary heap elements in O(log(n)) complexity

Question

i have written a binary heap that stores priority class(private members are PRIORITY and KEY). i wonder how i can change the priority of a element of heap in less than O(n) complexity when KEY of variable is given. thanks in advance

Answer 1

One way to solve this problem is have another structure(I'll call that auxiliary data structure). For instance a hash map(e.g. unordered_map) that maps keys to elements in the binary heap. You use this datastructure to find which element in the heap needs to have its priority modified. After you modify the priority of the element, you need to perform one sink and one sift operation with it. Both operations have complexity O(log(n)) thus overall the modification of priority has complexity O(log(n)). Here I assume you use an auxiliary data structure that supports find by key in complexity no more than O(log(n))(in case of hash map the complexity is O(1)).

Note you will have to modify the operations you've already implemented for the binary heap to keep the auxiliary data structure in sync with the binary heap.