Objective: Java Program You need to organize sheep in a heap. Fat sheep should g
ID: 3683172 • Letter: O
Question
Objective: Java Program
You need to organize sheep in a heap. Fat sheep should go on the bottom so they don’t 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 it’s 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 it’s 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 sheep’s 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
Explanation / Answer
Sheep.java
public class Sheep {
private double weight;
private String name;
public Sheep()
{
weight = 0.0;
name = "null";
}
public Sheep(double aWeight, String aName)
{
this.weight = aWeight;
this.name = aName;
}
public double getWeight() {
return weight;
}
public void setWeight(double weight) {
this.weight = weight;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String toString() {
return "Sheep [weight=" + weight + ", name=" + name + "]";
}
public int compareTo(Sheep sheep)
{
if (this.weight>sheep.weight)
return 1;
else if(this.weight<sheep.weight)
return -1;
else
return 0;
}
}
SheepHeapMain.java
public class SheepHeapMain {
private Sheep[]heap;
private static int size;
private static final int FIRST=1; //possibly needed, how do you do this
public SheepHeapMain()
{
heap = (Sheep[])(new Comparable[100]);
size = 0;
}
public SheepHeapMain(int aSize)
{
heap = new Sheep[aSize];
}
public void addSheep(Sheep val)
{
if(size >= heap.length)
{
System.out.println("Max size of heap has been reached");
return;
}
heap[size] = val;
climbUp();
size++;
}
public void climbUp()
{
int index = this.size;
while(index>0 &&//It has a parent
heap[index/2].compareTo(heap[index])<0)//And the value of the child is greater than the parent
{
//SWAP
Sheep temp = heap[index/2];
heap[index/2] = heap[index];
heap[index] = temp;
index = index/2;
}
}
public Sheep peek()
{
if(heap == null)
return null;
return heap[0];
}
public Sheep removeSheep()
{
System.out.println("removeSheep size: " + size + " array size: " + heap.length);
Sheep returnVal = peek();
heap[0] = heap[size-1]; //index Out of bonunds error
heap[size-1] = null;
size--;
climbDown();
return returnVal;
}
public void climbDown()
{
int index = 0;
while(index*2+1 < size)//While there is a left child
{
//Find smallest child
int bigIndex = index*2+1;
if(index*2+2 < size &&
heap[index*2+1].compareTo(heap[index*2+2])>0) //Right was bigger than left so change it
{
bigIndex = index*2+2;
}
if(heap[index].compareTo(heap[bigIndex])<0)//If current index is greater than smaller index
{
//SWAP
Sheep temp = heap[index];
heap[index] = heap[bigIndex];
heap[bigIndex] = temp;
}
else
{
break;//We're done!
}
index = bigIndex;//Update the index to continue
}
}
public void sheepRollCall()
{
for(Sheep thing : heap)
{
if(thing == null)
break;
System.out.println(thing.toString());
System.out.println("");
}
}
public static void sheepHeapSort(SheepHeapMain heap)
{
SheepHeapMain tempheap = heap;
for(int i=size;i>0;i++)
{
System.out.println(tempheap.removeSheep()+" ");
System.out.println();
}
}
}
SheepHeapTester.java
public class SheepHeapTester {
public static void main(String[] args) {
final int heapSize = 15;
SheepHeapMain heap = new SheepHeapMain(heapSize);
heap.addSheep(new Sheep(55,"Jimmy"));
heap.addSheep(new Sheep(43,"Ricky"));
heap.addSheep(new Sheep(77,"Larry"));
heap.addSheep(new Sheep(12,"Suzie Q"));
heap.addSheep(new Sheep(91,"Curly"));
heap.addSheep(new Sheep(85,"Bubba"));
heap.addSheep(new Sheep(189,"MEGA SHEEP"));
heap.addSheep(new Sheep(46,"Bo Peep"));
heap.addSheep(new Sheep(27,"Queenie"));
heap.addSheep(new Sheep(19,"Fluffy"));
System.out.println("current thing is");
heap.sheepRollCall();
System.out.println();
System.out.println("Sorted Sheepies :)");
SheepHeapMain.sheepHeapSort(heap);
}
}
output
Terminal
Sorted Sheepies :)
removeSheep size: 10 array size: 15
Sheep [weight=189.0, name=MEGA SHEEP]
removeSheep size: 9 array size: 15
Sheep [weight=77.0, name=Larry]
removeSheep size: 8 array size: 15
Sheep [weight=27.0, name=Queenie]
removeSheep size: 7 array size: 15
Sheep [weight=46.0, name=Bo Peep]
removeSheep size: 6 array size: 15
Sheep [weight=19.0, name=Fluffy]
removeSheep size: 5 array size: 15
Sheep [weight=55.0, name=Jimmy]
removeSheep size: 4 array size: 15
Sheep [weight=43.0, name=Ricky]
removeSheep size: 3 array size: 15
Sheep [weight=85.0, name=Bubba]
removeSheep size: 2 array size: 15
Sheep [weight=91.0, name=Curly]
removeSheep size: 1 array size: 15
Sheep [weight=12.0, name=Suzie Q]
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.