THIS NEEDS TO BE CODED IN JAVA. I WILL SUPPLY AN EXAMPLE FROM CLASS. USE THIS EXAMPLE AND MODIFY IT TO SOLVE THE PROBLEM. MUST BE DONE WITH AN ARRAY HEAP IMPLEMENTATION.

Code example:

public class ArrayHeap //comparable is an interface { private T[] heap; public static final int DEF_SIZE = 128; private int tailIndex; public ArrayHeap() { heap = (T[])(new Comparable[DEF_SIZE]); tailIndex = 0; } public ArrayHeap(int aSize) { if(aSize <= 0) { return; } heap = (T[])(new Comparable[aSize]); tailIndex = 0; } public void insert(T data) { if(tailIndex >= heap.length) { return; //heap is full } heap[tailIndex] = data; this.bubbleUp(); tailIndex++; } private void bubbleUp() { int tempIndex = this.tailIndex; //sets at the tail while(tempIndex > 0 && heap[(tempIndex - 1) / 2].compareTo(heap[tempIndex]) < 0) { //swap T temp = heap[(tempIndex - 1) / 2]; heap[(tempIndex - 1) / 2] = heap[tempIndex]; heap[tempIndex] = temp; tempIndex = (tempIndex - 1) / 2; } } public T remove() { T retVal = heap[0]; heap[0] = heap[tailIndex - 1]; //set root to last element heap[tailIndex - 1] = null; tailIndex--; this.bubbleDown(); return retVal; } private void bubbleDown() { int tempIndex = 0; //sets at the root while(((tempIndex * 2) + 1) < tailIndex) { //find larger child int bigIndex = tempIndex * 2 + 1; //assume left child is bigger if(((tempIndex * 2) + 2) < tailIndex && heap[(tempIndex * 2) + 1].compareTo(heap[(tempIndex * 2) + 2]) < 0) { bigIndex = tempIndex * 2 + 2; //there is a right child and it is bigger } //compare child to parent if(heap[tempIndex].compareTo(heap[bigIndex]) < 0) //parent smaller than child { //swap T temp = heap[tempIndex]; heap[tempIndex] = heap[bigIndex]; heap[bigIndex] = temp; } else { break; } tempIndex = bigIndex; } } public void heapSort() //destroys heap { for(int i = tailIndex; i > 0; i--) { System.out.println(this.remove()); } } }

MUST BE DONE WITH ARRAY HEAP IMPLEMENTATION.

Objective:

You need to organize sheep in a heap. Fat sheep should go on the bottom so they dont crush the skinny sheep.

Sheep have:

o Name

o Weight

The heap (HINT: min-heap) should have the following methods:

o addSheep: inserts a new instance of a sheep. The sheep should be added to the bottom of the heap and it is expected to climb up the heap until its on top of a heavier sheep but below a light sheep.

o climbUp: used by addSheep to allow the sheep to climb the heap and get in the right place.

o removeSheep: removes the sheep from atop the heap. Then the sheep on the bottom of the heap, is put on the top and climbs down until its where it needs to be.

o climbDown: Used by remove sheep to move the sheep down to the right place. Always pick the lighter of the sheep below it and swap if the current sheep is heavier than the lighter one.

o sheepRollCall: Print out the sheeps name and weight in breadth order

o sheepHeapSort: return a sorted array of sheep

Finally write a test file that demonstrates your sheep heaping abilities.

o It should add 15 sheep

o Remove at least 5

o Demonstrate that these work by calling the sheep roll call

o Then show the sheep heap sort works