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?

  • $\begingroup$ Really arbitrary delete? I only have seen delete-min, which merges the trees at the two children of the root. $\endgroup$ Feb 24, 2013 at 17:31
  • $\begingroup$ 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. $\endgroup$
    – kenor
    Feb 24, 2013 at 17:39
  • 3
    $\begingroup$ $\log(x+y) \le \log(xy) \le \log((x+y)^2) = 2\log(x+y)$ (assuming both $x$ and $y$ are positive) $\endgroup$
    – JeffE
    Feb 26, 2013 at 5:58

1 Answer 1


For the time complexity of merging, JeffE already pointed out in the comments that $O(\log(n_1n_2)) \in O(\log(n_1+n_2))$.

For arbitrary deletions note the following:

  • When we merge the two subtrees of the deleted node, the root of the resulting tree will have an s-value that is at least the s-value of the deleted node -1.
  • Thus, the s-value of any updated node will not be decreased by more than 1. (There is no constant bound for how much it can increase.)
  • Thus, if we update the s-value of a left child in and that value was strictly larger than the s-value of the right child, the s-values of the parent and all nodes above the parent will not change.
  • If the s-value of the left child and right child are equal, exchanging them still gives a valid leftist heap.
  • Thus, the number of updated nodes is bound by the length of a right flank in a leftist tree, which in turn is bound by $O(\log n)$.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.