I have been trying to implementing heap data structures for use in my research work. As part of that, I am trying to implement increase-key
operations for min-heaps. I know that min-heaps generally support decrease-key
. I was able to write the increase-key
operation for a binary min-heap, wherein, I exchange increased key with the least child recursively. In the case of the Fibonacci heap, In this reference, they say that the Fibonacci heap also supports an increase-key
operation. But, I couldn't find anything about it in the original paper on Fibonacci Heaps, nor could I find anything in CLRS (Introduction to Algorithms by Cormen).
Can someone tell me how I can go about implementing the increase-key operation efficiently and also without disturbing the data structure's amortized bounds for all the other operations?