# Binomial heap multiplying nodes

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.

## 1 Answer

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

• 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)$? – HaloKiller Jun 1 '14 at 7:00
• @Trinarics: Yes, that is what I am saying. – A.Schulz Jun 1 '14 at 8:04