Please answer this in java. I posted a code from a previous assignment which is
ID: 3684010 • Letter: P
Question
Please answer this in java. I posted a code from a previous assignment which is very similar, but there are a couple extra methods needed. (Also my heapSort method is not correct). If it is not in this format I cannot use it. Thank You
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
public class MinHeap {
public static final int DEFAULT_SIZE=100;
private int[] heap;
private int size;//always assumed to look at the last open element
public MinHeap()
{
heap= new int[DEFAULT_SIZE];
size=0;
}
public MinHeap(int length)
{
if(length>0)
{
heap= new int[length];
size=0;
}
}
public void insert(int value)
{
if(size>=heap.length)
{
System.out.println("Filled up");
return;
}
heap[size]=value;
//bubble up
bubbleUp();
size++;
}
private void bubbleUp()
{
int index=this.size;
while(index>0)
{
int parentIndex=index%2!=0?(index-1)/2:(index-1)/2;
if(parentIndex>=0 && (heap[parentIndex])>heap[index])
{
//out of order, so swap
int temp=heap[parentIndex];
heap[parentIndex]=heap[index];
heap[index]=temp;
}
else
{
break;
}
index=parentIndex;
}
}
public int peek()
{
if(heap==null)
return 0;
return heap[0];
}
public int remove()
{
int retVal=peek();
heap[0]=heap[size-1];
heap[size-1]=0;
size--;
//bubble down
bubbleDown();
return retVal;
}
private void bubbleDown()
{
int index=0;
while(index*2+1<size)
{
int bigIndex=index*2+1;
if(index*2+2 < size && (heap[index*2+1])>heap[index*2+2])//assumes left is bigger than right
{
bigIndex=index*2+2;//nope right is bigger
}
if((heap[bigIndex])>heap[index])
{
//SWAP
int temp=heap[index];
heap[index]=heap[bigIndex];
heap[bigIndex]=temp;
}
else
{
break;
}
index=bigIndex;
}
}
public void printHeap()
{
for(int moo : heap)
{
if(moo==0)
break;
System.out.println(moo);
}
}
public void heapSort()
{
MinHeap tempHeap = new MinHeap(heap.length);
int [] cloneHeap=heap.clone();
for(int i=0;i<size;i++)
{
tempHeap.insert(cloneHeap[i]);
}
//heap sort
for(int i=size;i>=0;i++)
{
System.out.print(tempHeap.remove()+" ");
System.out.println();
}
}
}
Explanation / Answer
Heap Sort
Your Code
public class MinHeap {
public static final int DEFAULT_SIZE=100;
private int[] heap;
private int size;//always assumed to look at the last open element
public MinHeap()
{
heap= new int[DEFAULT_SIZE];
size=0;
}
public MinHeap(int length)
{
if(length>0)
{
heap= new int[length];
size=0;
}
}
public void insert(int value)
{
if(size>=heap.length)
{
System.out.println("Filled up");
return;
}
heap[size]=value;
//bubble up
bubbleUp();
size++;
}
private void bubbleUp()
{
int index=this.size;
while(index>0)
{
int parentIndex=index%2!=0?(index-1)/2:(index-1)/2;
if(parentIndex>=0 && (heap[parentIndex])>heap[index])
{
//out of order, so swap
int temp=heap[parentIndex];
heap[parentIndex]=heap[index];
heap[index]=temp;
}
else
{
break;
}
index=parentIndex;
}
}
public int peek()
{
if(heap==null)
return 0;
return heap[0];
}
public int remove()
{
int retVal=peek();
heap[0]=heap[size-1];
heap[size-1]=0;
size--;
//bubble down
bubbleDown();
return retVal;
}
private void bubbleDown()
{
int index=0;
while(index*2+1<size)
{
int bigIndex=index*2+1;
if(index*2+2 < size && (heap[index*2+1])>heap[index*2+2])//assumes left is bigger than right
{
bigIndex=index*2+2;//nope right is bigger
}
if((heap[bigIndex])>heap[index])
{
//SWAP
int temp=heap[index];
heap[index]=heap[bigIndex];
heap[bigIndex]=temp;
}
else
{
break;
}
index=bigIndex;
}
}
public void printHeap()
{
for(int moo : heap)
{
if(moo==0)
break;
System.out.println(moo);
}
}
public void heapSort()
{
MinHeap tempHeap = new MinHeap(heap.length);
int [] cloneHeap=heap.clone();
for(int i=0;i<size;i++)
{
tempHeap.insert(cloneHeap[i]);
}
//heap sort
for(int i=size;i>=0;i++)
{
System.out.print(tempHeap.remove()+" ");
System.out.println();
}
}
}
As I observed your code was fine except for the hep sort function.Just replace those functions with the one given in above program and It would work. Thanks!!