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?
First, note that increase-key must be 𝑂(log𝑛) if we wish for insert and find-min to stay 𝑂(1) as they are in a Fibonacci heap.
If it weren't you'd be able to sort in 𝑂(𝑛) time by doing 𝑛 inserts, followed by repeatedly using find-min to get the minimum and then increase-key on the head by 𝜔 with ∀𝑥:𝜔>𝑥 to push the head to the end.
Now, knowing that increase-key must be 𝑂(log𝑛), we can provide a straightforward asymptotically optimal implementation for it. To increase a node 𝑛 to value 𝑥, first you decrease-key(𝑛,−∞), then delete-min() followed by insert(𝑛,𝑥).
Refer here