Assignment Description:

JAVA Finding the kth smallest value in a collection of n values with a MinHeap is more efficient than using a straightforward algorithm

For this assignment you will:

Implement an array-based MinHeap and an interface MinHeapInterface In a driver class:

Note: The code for MaxHeap is available in lecture 8s slides

Generate a List of 50 random integers ranging from 0 - 100. The List can contain repeat values.

Display the List of integers

Write a helper method named getKthSmallest that takes a List of integers as a parameter and uses your MinHeap to find the kth smallest integer in the List and print it out. Do not sort the List!

Note: Suppose you have a List that, were you to sort it, starts with 1, 2, 2, 4, 5...etc, then you would say that 2 is the second and third smallest element in your List.

This is what I have so far, please help. Thank you!!

MinHeapInterface.java

public interface MinHeapInterface> { { /** Adds a new entry to this heap  * @param newEntry An object to be added */  void add(T newEntry); /** Removes and returns the smallest item in this heap.  * @return Either the smallest object in the heap or null (if heap is empty) */  T removeMin(); /** Retrieves the smallest item in this heap  * @return Either the smallest object in the heap or null (if heap is empty) */  T getMin(); /** Detects whether this heap is empty  * @return True if the heap is empty, false otherwise */  boolean isEmpty(); /** Gets the size of this heap  * @return The number of entries currently in the heap */  int getSize(); // Removes all entries from this heap void clear(); } }

MinHeap.java

import java.util.Arrays; public final class MinHeap >implements MinHeapInterface { private T[]heap; private int lastIndex; private static final int DEFAULT_CAPACITY=50; public Minheap() { this(DEFAULT_CAPACITY); } public MinHeap(int initialCapacity) { T[]tempHeap=(T[])new Comparable[initialCapacity+1]; heap = tempHeap; lastIndex=0; }//@Override public void add(T newEntry) { lastIndex++; //ensureCapacity(); int newIndex=lastIndex+1; int parentIndex=newIndex/2; while((parentIndex>0)&& newEntry.compareTo(heap[parentIndex]) < 0) { heap[newIndex]=heap[parentIndex]; newIndex = parentIndex; parentIndex = newIndex / 2; } heap[newIndex]=newEntry; // lastIndex++; //ensureCapacity(); } private void reheap(int rootIndex) { boolean done = false; T orphan = heap[rootIndex]; int leftChildIndex = 2 * rootIndex; while(!done && (leftChildIndex <= lastIndex)) { int smallerChildIndex = leftChildIndex; int rightChildIndex = /*2*/ rootIndex + 1; if ( (rightChildIndex <= lastIndex) && heap[rightChildIndex].compareTo(heap[smallerChildIndex]) < 0) { smallerChildIndex = rightChildIndex; } if(orphan.compareTo(heap[smallerChildIndex]) > 0) { heap[rootIndex] = heap[smallerChildIndex]; rootIndex = smallerChildIndex; leftChildIndex = 2 * rootIndex; } else done = true; } heap[rootIndex] = orphan; } public T removeMin() { T root = null; if (!isEmpty()) { root = heap[1]; heap[1] = heap[lastIndex]; lastIndex--; reheap(1); } return root; } public T getMin() { T root = null; if(!isEmpty()) root = heap[1]; return root; } public boolean isEmpty() { if(lastIndex < 1) return lastIndex < 1; } public int getSize() { return lastIndex; } }