hi I need in java I have these clases but not sure how they would work I have tr
ID: 3817801 • Letter: H
Question
hi I need in java I have these clases but not sure how they would work I have tried but everything I do give me error please help!!
Problem 1: Adding stuff.
A skeleton of the add method has been provided in the MinHeap class. Complete the method by implemening the algorithm demonstrated in class:
Add elemement to end of heap.
While element is not at top of heap and element’s parent > element:
Swap element with parent
Problem 2: The smallest child.
Complete the given smallestChild method, which will be needed by the remove method:
Given the index of a parent, this method returns the index of the smallest child, or -1 if the parent has no child (in which case the parent is not a parent, but that’s beside the point). If both children are the same, the method returns the index of the left child.
Problem 3: Removing the smallest element.
Complete the given remove method so that it removes and returns the smallest element in the heap. This method should make use of the smallestChild method from Problem 2.
Problem 4: Heap Sort.
Now that you (hopefully) have a functioning heap, write the static method heapSort in the Test class. Like the other sorting algorithms, heapSort takes an array as a parameter and sorts the array in ascending order. If you have a heap, the Heap Sort algorithm is very simple:
Traverse the array and add all the numbers to a heap.
Remove all the numbers from the heap and put them back into the array.
Test your heapSort method using the Test class.
also this is the test clase
//You will need the MinHeap and Test classes from CampusCruiser for this lab. As you might suspect, the MinHeap class implements a heap and the Test class, you know, tests stuff. Yay!
Problem 1: Adding stuff.
A skeleton of the add method has been provided in the MinHeap class. Complete the method by implemening the algorithm demonstrated in class:
Add elemement to end of heap.
While element is not at top of heap and element’s parent > element:
Swap element with parent
Problem 2: The smallest child.
Complete the given smallestChild method, which will be needed by the remove method:
Given the index of a parent, this method returns the index of the smallest child, or -1 if the parent has no child (in which case the parent is not a parent, but that’s beside the point). If both children are the same, the method returns the index of the left child.
Problem 3: Removing the smallest element.
Complete the given remove method so that it removes and returns the smallest element in the heap. This method should make use of the smallestChild method from Problem 2.
Problem 4: Heap Sort.
Now that you (hopefully) have a functioning heap, write the static method heapSort in the Test class. Like the other sorting algorithms, heapSort takes an array as a parameter and sorts the array in ascending order. If you have a heap, the Heap Sort algorithm is very simple:
Traverse the array and add all the numbers to a heap.
Remove all the numbers from the heap and put them back into the array.
Test your heapSort method using the Test class.
Explanation / Answer
/*
* The mysterious and magnificent heap.
* Useful for sorting and priority queueing!
* Order your free copy today! (Pay only shipping and handling.)
*/
import java.util.NoSuchElementException;
public class MinHeap {
private int[] heap; // The heap.
private int size; // Index of next available array slot.
/*
* Constructor. Creates an empty heap. Yipee.
*/
public MinHeap(int capacity)
{
heap = new int[capacity];
size = 0;
}
/*
* Returns true if the heap is empty.
*/
public boolean isEmpty()
{
return size == 0;
}
/**
* Adds a new integer to the heap.
* @param n integer to add
* @throws HeapFullException if heap is full
*/
public void add(int n)
{
if (size < heap.length) {
heap[size] = n;
shiftUp(size);
size++;
} else {
throw new HeapFullException();
}
}
private void shiftUp(int i) {
while (i > 0) {
if (heap[(i-1)/2] > heap[i]) {
swap((i-1)/2, i);
i=(i-1)/2;
}
else
break;
}
}
/**
* Given the index of a parent, returns the index of the smallest child,
* or -1 if no such child exists.
* @param current index of parent
* @return index of smallest child or -1
*/
private int smallestChild(int i) {
int right = 2*i + 1;
int left = 2*i + 2;
if (left >= size) {
return -1;
}
else {
if (right >= size ) {
return left;
}
if (heap[left] <= heap[right]) {
return left;
}
else {
return right;
}
}
}
/**
* Deletes and returns the smallest integer in the heap.
* @return smallest element in heap
* @throws NoSuchElementException if heap is empty
*/
public int remove()
{
if (size == 0) {
throw new NoSuchElementException();
} else {
int minElem = heap[0];
heap[0] = heap[size-1];
size--;
heapify(0);
return minElem;
}
}
private void heapify(int i) {
int minIndex = smallestChild(i);
if (minIndex == -1) {
return;
}
else if (heap[minIndex] >= heap[i]) {
minIndex = i;
}
if (minIndex != i) {
swap(i, minIndex);
heapify(minIndex);
}
}
/**
* Returns the heap as a string.
*/
public String toString()
{
String s = "";
for(int i=0; i<size; i++) {
s += i + ": " + heap[i] + " ";
}
return s;
}
/**
* Returns the heap as an array.
* @return array containing same elements as heap
*/
public int[] toArray()
{
int[] a = new int[size];
for(int i=0; i<size; i++) {
a[i] = heap[i];
}
return a;
}
/**
* Private swap method used by add and remove.
* Swaps the elements in the heap at the given indexes.
* @param x index of first element
* @param y index of second element
*/
private void swap(int x, int y)
{
int temp = heap[x];
heap[x] = heap[y];
heap[y] = temp;
}
public int[] heapSort() {
int[] sortedArray = new int[size];
while(!isEmpty()) {
int element = remove();
sortedArray[size] = element;
}
for (int i=0, j=sortedArray.length-1; i<j; i++,j--) {
int temp = sortedArray[i];
sortedArray[i] = sortedArray[j];
sortedArray[j] = temp;
}
return sortedArray;
}
/**
* Exception that can be thrown when heap is full.
*/
class HeapFullException extends RuntimeException {
// A long number with no meaning whatsoever...but makes Java happy!
public static final long serialVersionUID = 8320632366082135L;
}
}
--------------------------------------------------------------------------------------------------------------------------------------------
import java.util.Random;
public class Test {
private static Random rand = new Random();
public static void main(String[] args) {
testMinHeap();
}
/**
* Test method for MinHeap
*/
public static void testMinHeap()
{
int[] a = initRandom();
MinHeap h = new MinHeap(a.length);
for(int i=0; i<a.length; i++) {
h.add(a[i]);
}
print(a);
System.out.println("Smallest: " + h.remove());
int[] b = h.toArray();
print(b);
System.out.println("Heap Sort : ");
print(h.heapSort());
}
/**
* Returns an array of random length with random integers.
* @return random array
*/
private static int[] initRandom()
{
int[] a = new int[rand.nextInt(40)];
for(int i=0; i<a.length; i++) {
a[i] = rand.nextInt(100);
}
return a;
}
/**
* Prints the given array to standard output.
* @param a array to print
*/
private static void print(int[] a)
{
for(int i=0; i<a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.