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.