Min Fibonacci Heap - increase key
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 &gt; 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)$.