4
$\begingroup$

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?

|cite|improve this question
$\endgroup$
4
$\begingroup$

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)$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Would it be wrong to do it the way we do in binary heaps? By recursively sending it down the tree in which it is present. $\endgroup$ – braceletboy Aug 9 '19 at 16:55
  • $\begingroup$ Your method is deleting the node from the Fibonacci heap and inserting it into the root list. Why not use the process described in the above comment, which tries to push the increased key down the tree? $\endgroup$ – braceletboy Aug 9 '19 at 17:04
  • $\begingroup$ @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)$. $\endgroup$ – orlp Aug 9 '19 at 17:04
  • $\begingroup$ Okay, Thank you! $\endgroup$ – braceletboy Aug 9 '19 at 17:06
  • 1
    $\begingroup$ @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)$ $\endgroup$ – Hendrik Jan Aug 10 '19 at 13:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.