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) {...}