Following code contains most of a class which uses a linked binary tree approach to implement a heap.

Since we do not want to have to rewrite this code when the element type changes,

this class uses a Comparator to assist in ordering the elements.

You will need to complete the siftUpComparator() and siftDownComparator() methods.

I do rate the answer, so please answer it as accurate as possible.

package edu.buffalo.cse116; import java.util.Comparator; import java.util.NoSuchElementException; /** * This uses a heap to implement * * @author Lewis and Chase * @author Matthew Hertz * @version 4.0 * @param  Type of (Comparable) element to be stored in this priority queue. */ public class LinkedHeap extends BinaryTree { /** Stores the last node that we added to this structure. */ private BTNode lastNode; /** Comparator used to organize and order the elements in the heap. */ private Comparator comparator; /** Number of nodes/elements within this binary tree. */ private int size; /** * Creates a new (empty) heap which will uses the specified Comparator to order its elements. * * @param comp Comparator that this heap will use to order its elements. */ public LinkedHeap(Comparator comp) { comparator = comp; } /** * Returns the size of this BinarySearchTree object. * * @return the size of this BinarySearchTree object. */ @Override public int size() { return size; } /** * Adds the specified element to this heap in the appropriate position according to its key value. * * @param obj the element to be added to the heap * @return Since this method will always succeed, it only returns true. */ @Override public boolean add(T obj) { BTNode node = new BTNode<>(); node.setElement(obj); if (getRootNode() == null) { setRootNode(node); } else { BTNode nextParent = getNextParentAdd(); if (nextParent.getLeft() == null) { nextParent.setLeft(node); } else { nextParent.setRight(node); } node.setParent(nextParent); } lastNode = node; size += 1; siftUpComparator(node, obj); return true; } /** * Returns the node that will be the parent of the new node * * @return the node that will be the parent of the new node */ private BTNode getNextParentAdd() { BTNode result = lastNode; while ((result != getRootNode()) && (result.getParent().getLeft() != result)) { result = result.getParent(); } if (result != getRootNode()) { if (result.getParent().getRight() == null) { result = result.getParent(); } else { result = result.getParent().getRight(); while (result.getLeft() != null) { result = result.getLeft(); } } } else { while (result.getLeft() != null) { result = result.getLeft(); } } return result; } /** * Reorders this heap after creating the space for an element in the tree. * * @param node BTNode in our linked tree that needs to be filled * @param elem Element that we are adding to the tree */ private void siftUpComparator(BTNode node, T elem) { } /** * Remove the element with the lowest value in this heap and returns a reference to it. Throws an * EmptyCollectionException if the heap is empty. * * @return the element with the lowest value in this heap */ public T remove() { if (isEmpty()) { throw new NoSuchElementException("Cannot call remove on an empty LinkedHeap"); } BTNode rootNode = getRootNode(); T minElement = rootNode.getElement(); if (size() == 1) { setRootNode(null); lastNode = null; } else { BTNode nextLast = getNewLastNode(); if (lastNode.getParent().getLeft() == lastNode) { lastNode.getParent().setLeft(null); } else { lastNode.getParent().setRight(null); } T shuffleElem = lastNode.getElement(); rootNode.setElement(shuffleElem); lastNode = nextLast; siftDownComparator(rootNode, shuffleElem); } size -= 1; return minElement; } /** * Reorders this heap after unlinking the node that is actually removed. * * @param node BTNode in our linked tree from which our down shifting need to start * @param elem Element that was in the (now removed) node to be shifted into the tree. */ private void siftDownComparator(BTNode node, T elem) { } /** * Returns the node that will be the new last node after a remove. * * @return the node that willbe the new last node after a remove */ private BTNode getNewLastNode() { BTNode result = lastNode; while ((result != getRootNode()) && (result.getParent().getLeft() == result)) { result = result.getParent(); } if (result != getRootNode()) { result = result.getParent().getLeft(); } while (result.getRight() != null) { result = result.getRight(); } return result; } /** * Returns the element with the lowest value in this heap. Throws an EmptyCollectionException if the heap is empty. * * @return the element with the lowest value in this heap */ public T element() { if (isEmpty()) { throw new NoSuchElementException("Cannot call remove on an empty LinkedHeap"); } BTNode rootNode = getRootNode(); T minElement = rootNode.getElement(); return minElement; } }