MaxHeapTest.java: Develop a unit test for the MaxHeap class. Here is a test plan for MaxHeapTest.java. For example, a good test is to insert a series of increasing (or decreasing or random) keys into the heap and then check if the heap was formed properly. Another good test is to extract all keys out of the heap using extractMax and that should give us a sorted list (basically, heapsort). If our heap is generic, it will be easier to write unit tests using a heap of Integer objects. If we arent writing a generic MaxHeap, then we would have to create some Task objects to insert and test the heap.

=========================================================

Max-heap Unit Testing Plan

Plan for MaxHeapTest.java. We would use Task values if our MaxHeap isnt generic. If it is generic, we can simply use Integer objects.

Create an empty heap. Test the isEmpty method -- it should return true.

Create a heap with one element. Test the isEmpty method -- it should return false.

insert test: Create a heap with two elements using insert, then get a reference to the heap array and check if the elements are at the right places.

extractMax test 1: Create a heap with two elements using insert, then call extractMax twice and test to see if you get them in sorted order. This can also be used to test the max method.

extractMax test 2: Create a heap with three elements using insert, then call extractMax thrice and test to see if you get them in sorted order. This can also be used to test the max method.

increaseKey test 1: Create a heap with two elements using insert, then call increaseKey on one of the entries such that it moves up and test the heap array to see if it works

increaseKey test 2: Create a heap with three elements using insert, then call increaseKey on one of the entries such that it moves up and test the heap array to see if it works

checkIfMaxHeap: Write a helper function that takes a heap array and tests if the max-heap property is satisfied

checkIfSorted: Write a helper function that takes an array of elements and returns true if it is sorted, and false otherwise.

insertAscending test: Create a heap by inserting 1, 2, , n (as priority values). Then check if the resulting heap satisfies the max-heap property using checkIfMaxHeap helper method. Then extract all values and see if the output is sorted using the checkIfSorted helper method.

insertDescending test: Create a heap by inserting n, n-1, , 2, 1 (as priority values). Then check if the resulting heap satisfies the max-heap property using checkIfMaxHeap helper method. Then extract all values and see if the output is sorted using the checkIfSorted helper method.

insertRandom test: Create a heap by randomly inserting n random values (as priority values) in the range 1..n. Then check if the resulting heap satisfies the max-heap property using checkIfMaxHeap helper method. Then extract all values and see if the output is sorted using the checkIfSorted helper method.

The above plan for MaxHeapTest.java should provide sufficient confidence in using MaxHeap in the application. We dont really need to directly test buildMaxHeap, but we can test it indirectly by testing the constructor. You can certainly add to the above plan.