2
$\begingroup$

Input: A max binomial heap $H$, and a pointer to a node $V$.
Output: A max binomial heap, where all the children of $V$ are multiplied by 2.

I have tried solving this by taking out the node $V$ together with it's sub-tree, multiplying all the children of V by $2$, rearranging the heap to close the hole, and adding V's children to the heap.

It sums up to $O(k\log n )$, where $k$ is the number on nodes in the tree containing $V.$
Can I do better than this? I'm sure I can but I don't know how.

$\endgroup$
1
$\begingroup$

I think in this scenario you can just bubble-up one of the updated element to restore the max-heap property.

Notice that by the multiplication you have increased the keys in $V$ children. So the trees rooted at the children still have the max-heap property, but maybe $V$ does not anymore. You can repair this, by swapping the largest key of the children with the key of $V$. This restores the max-heap property for the subtree rooted at $V$. You continue by comparing the key of $V$ with the key of the father of $V$ and swap the key is necessary. You do this, until nothing was swapped, or you reach the root - its the typical heapify routine.

Since binomial heaps have depth at most $\log n$ and the degree is also bounded by $\log n$ the whole procedure needs $O(\log n)$.

$\endgroup$
  • $\begingroup$ What you are saying is just that I need to multiply them and let them percolate using heapify? If so, is it bounded by $O(logn)$? $\endgroup$ – HaloKiller Jun 1 '14 at 7:00
  • $\begingroup$ @Trinarics: Yes, that is what I am saying. $\endgroup$ – A.Schulz Jun 1 '14 at 8:04

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.