Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

The time complexity of merge (union) operation is said to be $O(\lg (n_1 + n_2))$, where $n_1$ and $n_2$ are the numbers of elements in the merged heaps, respectively. I do not understand this - the algorithm has to go through all the elements of both rightmost paths of the original heaps - lengths of these paths are bound by $O(\lg n_1)$ and $O(\lg n_2)$. That makes $O(\lg n_1 + \lg n_2)$ in total, which is $O(\lg (n_1 n_2))$. Where am I making a mistake in my assumptions?

Arbitrary delete operation - the complexity should be $O(\lg n)$, where $n$ is the size of the heap. But after the deletion, the algorithm has to go through all the nodes from the parent of the deleted node to the root and correct the Leftist property, and the lenght of this path is bound by $O(n)$. Again, where am I wrong?

share|improve this question
    
Really arbitrary delete? I only have seen delete-min, which merges the trees at the two children of the root. –  Hendrik Jan Feb 24 '13 at 17:31
    
Yes, arbitrary. I have seen multiple sources saying that arbitrary delete can be done in O(lg n) time provided you use an additional parent pointer for each node. –  kenor Feb 24 '13 at 17:39
1  
$\log(x+y) \le \log(xy) \le \log((x+y)^2) = 2\log(x+y)$ (assuming both $x$ and $y$ are positive) –  JeffE Feb 26 '13 at 5:58
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.