Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Merging two perfect binary heaps?

I've been stuck on a question for a while and was wondering if anyone can point me in the right direction:

Suppose binary heaps are represented using a pointer-based tree representation instead of an array. Consider the problem of merging binary heap LHS with RHS. Assume both heaps are full complete trees, containing (2^L - 1) and (2^R -1) nodes, respectively.
Give two O(log N) algorithms to merge the two heaps, one if L = R and one if |L - R| = 1.

This is a homework problem, I just need to be pointed in the right direction.

like image 836
user220755 Avatar asked Jan 22 '10 02:01

user220755


1 Answers

Hint for L=R: pretend you've just removed the root. Let me know if you need more.

like image 176
outis Avatar answered Sep 23 '22 22:09

outis