For this Java question(Eclipse), you will implement a heap structure by completing a class called MinHeap which extends a FullBinaryTree and also simultaneously implements the HeapADT interface. Further, the MinHeap class uses a generic type E which, itself, extends Comparable (meaning that MinHeap can be instantiated with any generic type E as long as E is a Comparable type, like a number or String or anything having a .compareTo() method on it).

The important functionality you will have to implement are the methods upHeap and trickleDown.

upHeap: This is called when a new element is added to the heap. A new element is first added at the end of the tree, and then upHeap will compare it to is parent node to see if it should come before the parent and swap upward. If it does swap upward, upHeap should be called again to further check if it needs to move higher.

trickleDown: After extracting the minimum element (the root node), the largest (last) element should replace the root node (thus reducing the final index by 1), and then this large value at the root should trickle down the tree to an appropriate position. In order to properly trickle down, it should check if it has a leftChild and a rightChild and the smaller of the two children (if they exist) should be swapped with the current position, if they come before it. When the current position swaps down to its child position, it should trickle down again from there.

The UseExample.java gives an example of how to use this MinHeap to perform HeapSort. Test your code by sorting a variety of arrays.

Please read the question carefully, there are total 4 classes, only two classes need to add some codes to complete the program(FullBinaryTree and MinHeap), I put a TODO sign in them. Thank you very much! Here are the four classes we need for this question:

import java.util.ArrayList;

/** * A class representing a full binary tree, implemented on an * ArrayList. Complete the methods to retrieve the left and right * child indexes, as shown in class with the array implementation of * a fullBinaryTree. * You will also have to extend this class with your MinHeap implementation. */

public class FullBinaryTree {

protected ArrayList nodes; public FullBinaryTree() { //Do not edit. nodes = new ArrayList(); } public int size() { //Do not edit. return nodes.size(); } /** * Returns the INDEX of where the left child would be, if it exists. */ protected static int leftChild(int i) { //TODO: return the index of the left child return 0; } /** * Returns the INDEX of where the right child would be, if it exists. */ protected static int rightChild(int i) { //TODO: return the index of the right child return 0; } /** * Returns the index of the parent node of i. For convenience, the * parent of the root is the root. */ public int parent(int i) { //TODO: if i=0, return 0. Else, return (i-1)/2 return 0; }

/** * Adds an element to the full binary tree, just at the end of the tree. * This method is not really used -- you should be overwriting it * in your MinHeap class. * @param e */ public void add(E e) { //Do not edit. nodes.add(e); } }

/** * This interface is complete. You do not need to edit this file. * You must implement this interface with a MinHeap class. * @param */ public interface HeapADT { /** * Add an element to the minHeap * @param e */ public void add(E e);

/** * Remove and return the root of the minHeap * @return */ public E poll();

/** * Return (and do not remove) the root of the minHeap * @return */ public E peek();

/** * Return the number of elements in the minHeap * @return */ public int size();

}

/** * MinHeap of Comparables. Two E objects which extend Comparable can * be compared by e1.compareTo(e2), and if this results in a negative * value, e1 comes before e2. If it results in a positive value, e2 comes * first. * This class extends fullBinaryTree, meaning we can use the left and right * child functions to get the index of child nodes. But it must also support * heap functionality, like up-heap, trickle-down, and extract-min. * @param */

public class MinHeap> extends FullBinaryTree implements HeapADT {

/** * Constructs the underlying ArrayList called 'nodes' */ public MinHeap() { // Nothing to change here. super(); } @Override public E poll() { //TODO: Get (and remove) the root element. If there are any //elements left, extract the last element of nodes and //place it into the root position. Then call trickleDown(0) before //returning the original root. return null; }

private void trickleDown(int i) { //TODO: To trickle-down at index i: //IF the leftChild exists and comes before i, swap it up. //IF the rightChild exists and comes before i, swap it up. }

@Override public E peek() { //TODO: return the root, without removing it return null; } @Override public void add(E e) { //TODO: add an element at the end of nodes, then //call upHeap on the last index. }

private void upHeap(int index) { //TODO: If index==0, you are done. Otherwise, if the element at //index comes before its parent, swap it with its parent and then //call upHeap on the parent index. } public String toString() { // Nothing to change here. return nodes.toString(); } }

import java.util.ArrayList;

public class UseExample {

public static void main(String[] args) { String[] words = {"word", "so", "many", "words","i", "sure", "do", "enjoy", "java", "programming", "and", "this", "seems", "to", "be", "enough"};

ArrayList sorted = heapSort(words);

System.out.println(sorted); /* Should output: * [and, be, do, enjoy, enough, i, java, many, programming, seems, so, sure, this, to, word, words] */ }

private static ArrayList heapSort(String[] words) { MinHeap m = new MinHeap<>(); for (String s:words) m.add(s); ArrayList output = new ArrayList(); while (m.size() > 0) { output.add(m.poll()); } return output; }

}