I want to merge $2$ binary heaps. Which is the fastest algorithm to do so. Also would like to know its time complexity.

I know how to do it linear time $O(n)$, I want to know if there is something faster (probably there is).

  • 2
    $\begingroup$ Possible duplicate of cs.stackexchange.com/questions/72600/… $\endgroup$
    – user35837
    Oct 21 '17 at 15:37
  • $\begingroup$ This is a question & answers site, not an algorithms archive. $\endgroup$
    – Raphael
    Oct 21 '17 at 16:20
  • $\begingroup$ Why would you expect an algorithm in $o(n)$ time? That would mean that can only look at very few nodes. $\endgroup$
    – Raphael
    Oct 21 '17 at 16:21
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$
    – ryan
    Oct 21 '17 at 23:31

It is possible to merge two standard binary heaps in $\mathcal O(\log n)$ time, picking $\pm\infty$ setting the both heaps as children and then extracting top element (this operation takes $\mathcal O(\log n)$ time).

You might be also interested in paper about faster merge in $\log k * \log n$, but it is non-standard, pointer based implementation. The standard approach is to use array. The other operations take a bit longer though.

Another idea is to use Binomial heap or Leftist heap, with merge operation in $\mathcal O(\log n)$ time or Fibonacci, Pairing, Brodal or Rank-pairing heap to support merge in $\Theta(1)$ time.

The list is described at Wikipedia, Binomial heap. Although marvelous at first glance they hide larger constant and increase time of standard operations on heaps, for example find min may be $\mathcal O(\log n)$ instead of $\Theta(1)$.

If you want the asymptoticaly fastest algorithm then any of mentioned are good. For practical purposes I would recommend the Pairing heap, which is a form of multiway tree, easy to implement (comparing with Brodal for example).

  • $\begingroup$ I don't care about the copies. Lets say theorically we don't copy anything, Can you give me the fastest algoritm $\endgroup$ Oct 21 '17 at 17:23
  • $\begingroup$ I don't think this answer hits the mark; we may be able to link the two heaps (in tree representation) together without inspecting every node. (Not that I think it's likely, but the argument is not solid on its own.) $\endgroup$
    – Raphael
    Oct 21 '17 at 18:58

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.