 The best you can do is (in case of array implementation) simply concatenating the two heap arrays and build a heap of the result.A heap on "n" elements can be merged with a heap on "k" elements using O(log "n" log "k") key comparisons, or, in case of a pointer-based implementation, in O(log "n" log "k") time.An algorithm for splitting a heap on "n" elements into two heaps on "k" and "n-k" elements, respectively, based on a new view
of heaps as an ordered collections of subheaps was presented in.