Homework: Heapsort

1. Given the following heap, where the items are integers and the heap is ordered according to the <= relation:

                 2
               /   \
              5     6
             / \   /
            8   5 7 

   Draw the five heaps resulting from removing each of the first five items in the ordering using the algorithm discussed in class (see Slides 26-32 in Heaps and Heapsort).
2. Write the body of the following static method, which returns true if and only if the given BinaryTree<Integer>, t, satisfies the heap ordering property according to the <= relation. (Note that this says nothing about the shape of the tree, i.e., it should work whether or not t is a complete binary tree, and should not check whether it is.)

       /**
        * Checks if the given {@code BinaryTree<Integer>} satisfies the heap
        * ordering property according to the <= relation.
        * 
        * @param t
        *            the binary tree
        * @return true if the given tree satisfies the heap ordering property;
        *         false otherwise
        * @ensures <pre>
        * satisfiesHeapOrdering = [t satisfies the heap ordering property]
        * </pre>
        */
       private static boolean satisfiesHeapOrdering(BinaryTree<Integer> t) {...}
   

3. Draw and complete the commutativity diagram on Slides 18-23 in More About Heaps.

Additional Questions

1. Think about what it would take to decide if a given binary tree satisfies the heap shape property, i.e., to decide if the binary tree is complete.
2. Write the body of the following static method.

       /**
        * Checks if the given {@code BinaryTree<T>} is complete.
        * 
        * @param <T>
        *            type of {@code BinaryTree} entries
        * @param t
        *            the {@code BinaryTree}
        * @return true if the given tree is complete; false otherwise
        * @ensures isComplete = [t is complete]
        */
       private static <T> boolean isComplete(BinaryTree<T> t) {...}