# Min Fibonacci Heap - increase key

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 $$\text{increase-key}$$ must be $$O(\log n)$$ if we wish for $$\text{insert}$$ and $$\text{find-min}$$ to stay $$O(1)$$ as they are in a Fibonacci heap.
If it weren't you'd be able to sort in $$O(n)$$ time by doing $$n$$ $$\text{insert}$$s, followed by repeatedly using $$\text{find-min}$$ to get the minimum and then $$\text{increase-key}$$ on the head by $$\omega$$ with $$\forall x:\omega > x$$ to push the head to the end.
Now, knowing that $$\text{increase-key}$$ must be $$O(\log n)$$ we can provide a very simple asymptotically optimal implementation for it. To increase a node $$n$$ to value $$x$$, first you $$\text{decrease-key}(n, -\infty)$$, then $$\text{delete-min()}$$ followed by $$\text{insert}(n, x)$$.
• @braceletboy I don't know enough about Fibonacci heaps to see whether that would be permissible, sorry. As for any alternative implementation, they will fundamentally have the same amortized asymptotic cost: $O(\log n)$. – orlp Aug 9 '19 at 17:04
• @braceletboy In most heap ordered structures one can move values in the tree like you describe. But is not always guaranteed that the depth of branches are indeed bounded by $O(\log n)$ – Hendrik Jan Aug 10 '19 at 13:11