tags:

views:

317

answers:

1
+6  Q: 

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 if L = R and if |L - R| = 1

note: this is a homework problem, i just need to be pointed in the right direction

+4  A: 

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

outis  2010-01-22 03:03:31
Thank you so much! I get it now!
 2010-01-22 03:08:57
This is a good hint. What I can't figure out is, what is the prof. getting at with the |L-R| = 1? Seems like the algorithm that is the result of your hint would work in that case as well.
PeterAllenWebb  2010-01-22 03:09:56
Think about the properties of an array-based heap, and how the algorithm hinted at would violate some of these properties if |L-R|=1. Actually, it's not just array-based heaps; think about the shape property.
outis  2010-01-22 03:14:43

related questions

Java Time Zone is messed up
Eclipse on win64
Automate builds for Java RCP for deployment with JNLP
Why are professors or schools picking Java over C++ to teach to students?
Is there a real benefit of using J#?
Public/Popular Websites using JavaServer Faces
Why can't I use a try block around my super() call?
Accessing post variables using Java Servlets
Personal Linux web server
Is this really widening vs autoboxing?
How can I Java webstart multiple, dependent, native libraries?
Why can't I call toString() on a Java primitive?
How do I use Java to read from a file that is actively being written?
What code analysis tools do you use for your Java projects?
IllegalArgumentException or NullPointerException for a null parameter?
How do I configure and communicate with a serial port?
What is the best way to parse strings in Java
Getting started with a custom JXTA PeerGroup
Creating a custom button in Java
How to get started "writing" a code coverage tool?
Which Build-/Configuration Management Tool?
What is the difference between an int and an Integer in Java/C#?
What is the meaning of the type safety warning in certain Java generics casts?
How would you access Object properties from within an object method?
Converting CSV File to XML in Java