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.

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

here is max heap:

public class MaxHeap {

private Task[] heap;

private int size;

public MaxHeap() {

heap = new Task[10];

size = 0;

}

public MaxHeap(Task[] tasks) {

heap = tasks;

size = tasks.length;

buildMaxHeap();

}

public void heapify(int i) {

int l = left(i);

int r = right(i);

int largest;

if (l < size && heap[l].getKey() > heap[i].getKey()) {

largest = l;

} else {

largest = i;

}

if (r < size && heap[r].getKey() > heap[largest].getKey()) {

largest = r;

}

if (largest != i) {

swap(i, largest);

heapify(largest);

}

}

public Task max() {

return heap[0];

}

public Task extractMax() {

if (size < 1) {

return null;

}

Task max = heap[0];

heap[0] = heap[size - 1];

size--;

heapify(0);

return max;

}

public void insert(Task task) {

if (size == heap.length) {

Task[] newHeap = new Task[heap.length * 2];

System.arraycopy(heap, 0, newHeap, 0, heap.length);

heap = newHeap;

}

int i = size;

size++;

while (i > 0 && heap[parent(i)].getKey() < task.getKey()) {

heap[i] = heap[parent(i)];

i = parent(i);

}

heap[i] = task;

}

public void increaseKey(int i, int key) {

if (key < heap[i].getKey()) {

return;

}

heap[i].setKey(key);

while (i > 0 && heap[parent(i)].getKey() < heap[i].getKey()) {

swap(i, parent(i));

i = parent(i);

}

}

public boolean isEmpty() {

return size == 0;

}

private void buildMaxHeap() {

for (int i = parent(size - 1); i >= 0; i--) {

heapify(i);

}

}

private int parent(int i) {

return (i - 1) / 2;

}

private int left(int i) {

return 2 * i + 1;

}

private int right(int i) {

return 2 * i + 2;

}

private void swap(int i, int j) {

Task temp = heap[i];

heap[i] = heap[j];

heap[j] = temp;

}

}