CSE 321 Homework 4

1. Given the following ARE_IN_ORDER heap, where the items are integers and ARE_IN_ORDER (x, y) = (x >= y): Draw the five heaps resulting from removing each of the first five items in the ordering.

2. Write the body of the Boolean function Satisfies_Ordering_Property which returns true if and only if the given binary tree of integer, t, satisfies the heap ordering property. (Note that this says nothing about the shape of the tree.) Assume that ARE_IN_ORDER is defined to be the usual <= relation on integers.

       global_function Boolean Satisfies_Ordering_Property (
               preserves Binary_Tree_Of_Integer& t
           );
       /*!
   	ensures
   	    Satisfies_Ordering_Property =
   		[t satisfies the heap ordering property]
       !*/
   

3. Think about what it would take to decide if a given binary tree satisfies the heap shape property, i.e., to decide if the tree is complete. Briefly describe your ideas.