CMSC 341 -- Spring 2004 -- Project 5 Questions

Copy this file into your directory and edit it to add your answers
to the following questions about project 5.

This questions count for 10% of your project grade.

Outline an algorithm that merges two intervals heaps I1 and I2 
into a binary tree. The resulting tree needs not be a complete 
binary tree, but it must obey the interval heap order property, 
that is, the interval at any non-leaf node contains intervals 
of its children. 

Your algorithm should have time performance of 
O(max(depth(I1), depth(I2)).

Hint: Since the resulting tree is not necessarily a CBT, 
it should not be implemented as an array. Also, do not attempt
to extend Leftist heap and its meld operation to interval
heaps, it is unnecessary and difficult, if not impossible.

ANSWER:
-Create a new empty tree BT.  

-Starting at the first node of I1 and I2: create tree node in BT.
This new node will have an interval of [ min(node(I1),node(I2)),
max(node(I1,I2)) ].  The 2 keys not inserted into BT will be
reinserted into I1.  Repeat for left and right children of
visited nodes in I1 and I2 (inserting into left and right 
children in BT respectively).  Repeat this until all
nodes have been visited in I1 and I2.

-This should run in O( max(depth(I1),depth(I2) ) )