Question

Check if an array is a heap in Java.

Complete the method isHeapTree

Together, these methods are meant to determine if an array of objects corresponds to a heap. The methods are generic, and they should work with an array of any type T that implement Comparable<T>.

Implement the second method so that it uses recursion to process the complete tree/subtree whose root is at position i in the array arr. The method should return true if that tree/subtree is a heap, and false if it is not a heap. A leaf node is the root of a heap with only one node.

Note that the first method – which is a public wrapper method for the method that you will write – makes the initial call to your method with a value of 0 for i, which means that it will determine if the complete tree represented by the full array is a heap. You should not modify this wrapper method.

In implementing your recursive method, you may find it helpful to review:

• the arithmetic rules for navigating through a complete tree that is stored in an array

• how the compareTo() method can be used to compare two objects.

There is also a main() method with one unit test. You should add at least two other tests.

public class theHeap {

    public static <T extends Comparable<T>> boolean isHeap(T[] arr) {

        if (arr == null || arr.length == 0) {

            return false;

        }

        return isHeapTree(arr, 0);

    }

    private static <T extends Comparable<T>> boolean isHeapTree(T[] arr, int i) {

        // Implement this method.

    }

    public static void main(String[] args) {

        System.out.println("--- testing isHeapTree() ---");

        System.out.println();

        System.out.println("(0) an array of integers that is a heap");

        try {

            // Note that we need to use the wrapper class (Integer)

            // instead of the primitive type (int).

            Integer[] arr1 = { 50, 30, 35, 25, 23, 13, 18, 8, 20, 16 };

            boolean results = isHeap(arr1);

            System.out.println("actual results:");

            System.out.println(results);

            System.out.println("expected results:");

            System.out.println(true);

            System.out.print("MATCHES EXPECTED RESULTS?: ");

            System.out.println(results == true);

        } catch (Exception e) {

            System.out.println("INCORRECTLY THREW AN EXCEPTION: " + e);

        }

        System.out.println(); // include a blank line between tests

        /*

         * Add at least two additional unit tests. Follow the same format that we have

         * used above.

         */

    }

}

Answer 1

Answer:

Note:

• The fourth test case requires an addition class. It performs the testcase based on the user defined class called Person.
• So, before executing, please make sure the provided Person is also placed in the same folder as that of the theHeap class.
• If not, the fourth test case and Person class can be removed.

Program code screen shot: