come up with a strategy to combine two binary heaps in logn

Solution

You probably can\'t do better than linear time when merging simple array-based binary heaps. If you want cheap merging, you should choose a different heap representation, such as binomial heaps or leftist heaps (leftist heaps are a bit easier to implement IMO). If amortized bounds are sufficient, you could try skew heaps (even simpler to implement). If you want something exotic and not entirely understood, but performant, try pairing heaps. These all support O(lgn)O(lgn) merging.

One of the best resources covering these various data structures is Chris Okasaki\'s \"Purely Functional Data Structures.\" You can find it in thesis form online (eg, here), but you need the book for the really good stuff. Among other things he develops lazy versions of some of these data structures that attain their amortized bounds even in fully persistent settings (where past versions of a data structure can updated and queried in the same way as a recently created one, a natural guarantee in a setting without destructive updates). The exposition is one of the best I\'ve seen, even if you aren\'t constrained to or interested in a purely functional setting.