# reordering a max heap that the values of one of her subtrees has been changed

Let $$H$$ be a max binary heap with $$n$$ elements (vertexes).

Pick a vertex $$z$$ in the heap with height of $$k$$ ($$0)

To every element in the sub heap of $$z$$ we add the constant value $$c > 0$$.

We need to fix $$H$$ to be again a max heap, withour changing the value of the elements in the heap.

We need to do it with run time of $$O(2^k \cdot \lg n)$$.

I know that $$MAX-HEAPIFY$$ takes $$O(\lg n)$$ and $$2^k$$ is the number of leafs in a tree with hright of $$k$$.

But i dont realy have an idea for an algoritm.

Any directions?

Thanks.

It seems like you can do it in $$O(k\log{}n)$$ time. Just compare vertex $$z$$ with its parent $$p$$. If $$z$$ has lesser value then we are done. Else swap $$z$$ with $$p$$ and heapify subtree rooted in $$p$$. The vertex $$z$$ will be raised no more than $$k$$ times and each raise takes $$O(\log{}n)$$
• $f \in O(k\log n) \implies f \in O(2^{k}\log n)$ So we can say that the presented algorithm runs in $O(2^{k}\log n)$ time. Does it solve your problem? – Vladislav Bezhentsev Apr 16 at 0:45