please use java. do not need to compile. just write the code. thanks import java
ID: 3919157 • Letter: P
Question
please use java. do not need to compile. just write the code. thanks
import java.util.Comparator;
public class BinaryMinHeap<T>
{
private ArrayList<T> array;
private Comparator<T> comparator;
public BinaryMinHeap(int capacity, Comparator<T> comparator)
{
array = new ArrayList<T>(capacity + 1);
array.add(null); // Index zero is unused
this.comparator = comparator;
}
private static final int ROOT = 1;
private static int left(int i)
{
return 2 * i;
}
private static int right(int i)
{
return 2 * i + 1;
}
private static int parent(int i)
{
return i / 2;
}
private int minChild(int i)
{
int leftChild = left(i);
int rightChild = right(i);
// If both a left and right child exist,
// take the smaller of the two.
if (rightChild < array.size() &&
comparator.compare(array.get(rightChild), array.get(leftChild)) < 0)
{
return rightChild;
}
else
{
return leftChild;
}
}
public boolean isEmpty()
{
return array.size() < 2; // First element doesn't count
}
public void add(T element)
{
// Resizes the array if necessary
array.add(element);
// A potential location for the new element; may violate the heap rule
int hole = array.size() - 1;
// Promote the new element until its not needed,
// or it reaches the top of the heap
while(hole > ROOT &&
comparator.compare(element, array.get(parent(hole))) < 0)
{
array.set(hole, array.get(parent(hole)));
hole = parent(hole);
}
// Actually store the new element in its final position in the heap.
array.set(hole, element);
}
public T remove()
{
// Save the element being removed
T element = array.get(1);
// Save the element whose position is being removed,
// and remove its original position.
int hole = ROOT;
T movingElement = array.get(array.size() - 1);
array.remove();
// Skip this when removing the last element
if (array.size() >= 2)
{
// Determine the child to promote, if needed
int minChild = minChild(hole);
// Promote elements until it's not needed,
// or we reach the bottom of the heap
while(minChild < array.size() &&
comparator.compare(array.get(minChild), movingElement) < 0)
{
array.set(hole, array.get(minChild));
hole = minChild;
minChild = minChild(hole);
}
// Store the moving element in its final position in the heap.
array.set(hole, movingElement);
}
// Return the element that was original removed (the old root)
return element;
}
public static void main(String[] args)
{
BinaryMinHeap<Integer> minHeap1 =
new BinaryMinHeap<Integer>(7, Comparator.naturalOrder());
minHeap1.add(4);
minHeap1.add(7);
minHeap1.add(1);
minHeap1.add(6);
minHeap1.add(2);
minHeap1.add(3);
minHeap1.add(5);
System.out.println(minHeap1.array);
BinaryMinHeap<Integer> minHeap2 =
new BinaryMinHeap<Integer>(7, Comparator.naturalOrder());
minHeap2.add(7);
minHeap2.add(1);
minHeap2.add(5);
minHeap2.add(2);
minHeap2.add(3);
minHeap2.add(6);
minHeap2.add(4);
System.out.println(minHeap2.array);
BinaryMinHeap<Integer> minHeap3 =
new BinaryMinHeap<Integer>(9, Comparator.naturalOrder());
minHeap3.add(1);
minHeap3.add(2);
minHeap3.add(3);
minHeap3.add(17);
minHeap3.add(19);
minHeap3.add(36);
minHeap3.add(7);
minHeap3.add(25);
minHeap3.add(100);
System.out.println(minHeap3.array);
minHeap3.remove();
System.out.println(minHeap3.array);
BinaryMinHeap<Integer> minHeap4 =
new BinaryMinHeap<Integer>(9, Comparator.naturalOrder());
minHeap4.add(-100);
minHeap4.add(-19);
minHeap4.add(-36);
minHeap4.add(-17);
minHeap4.add(-3);
minHeap4.add(-25);
minHeap4.add(-1);
minHeap4.add(-2);
minHeap4.add(-7);
System.out.println(minHeap4.array);
minHeap4.remove();
System.out.println(minHeap4.array);
BinaryMinHeap<Double> minHeap =
new BinaryMinHeap<Double>(16, Comparator.naturalOrder());
for (int i = 0; i < 32; i++)
{
minHeap.add(Math.random() * 100);
}
System.out.println(minHeap.array);
while (!minHeap.isEmpty())
{
System.out.println(minHeap.remove());
}
}
}
4 Heap-Sort Heap-Sort is another tree-based sorting algorithm discussed briefly in lecture. The steps of Heap-Sort are: Fill an initially empty binary min-heap with the elements of the unsorted list. .Remove elements one-by-one and add them, in order, to a new array. Using the implementation of BinaryMinHeap.java from lecture, implement HeapSort. The signature for the method should be: public static Object[] heapSort (Tl] original, Comparator Write several test cases for Heap-Sort and demonstrate to a TA that they pass. comp)Explanation / Answer
public static <T> void heapSort(T[] original, Comparator<T> comp) {
int n = original.size();
for (int rootIndex = n/2 - 1; rootIndex >= 0; rootIndex--)
reheap(original, rootIndex, n - 1);
swap(original, 0, n - 1);
for (int lastIndex = n - 2; lastIndex > 0; lastIndex--) {
reheap(original, 0, lastIndex);
swap(original, 0, lastIndex);
}
}
private static <T extends Comparable<? super T>> void reheap(T[] heap, int rootIndex, int lastIndex) {
boolean done = false;
T orphan = heap[rootIndex];
int leftChildIndex = 2 * rootIndex + 1;
while (!done && (leftChildIndex <= lastIndex)) {
int largerChildIndex = leftChildIndex;
int rightChildIndex = leftChildIndex + 1;
if ( (rightChildIndex <= lastIndex) &&
heap[rightChildIndex].compareTo(heap[largerChildIndex]) > 0) {
largerChildIndex = rightChildIndex;
} // end if
if (orphan.compareTo(heap[largerChildIndex]) < 0) {
heap[rootIndex] = heap[largerChildIndex];
rootIndex = largerChildIndex;
leftChildIndex = 2 * rootIndex + 1;
}
else
done = true;
}
heap[rootIndex] = orphan;
}
private static void swap(Object[] a, int i, int j) {
Object temp = a[i];
a[i] = a[j];
a[j] = temp;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.