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

Pick a vertex $z$ in the heap with height of $k$ ($0<k<\lg n$)

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?



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

| cite | improve this answer | |
  • $\begingroup$ Yes thanks, but, if i understood you correctly thats the previous sub question, which i have already did, i have to do it with the run time i showed above. $\endgroup$ – Alon Apr 15 at 23:59
  • $\begingroup$ $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? $\endgroup$ – Vladislav Bezhentsev Apr 16 at 0:45

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.