Question

Since we do not want to have to rewrite this code when the element type changes, this classes uses a Comparator to assist in ordering the elements. You will need to complete the siftUpComparator() and siftDownComparator() methods in the LinkedHeap Class.

siftUp

§Added element may violate heap-order property

§siftUp() restores order starting at added node

§Processing will continue working up the tree until:

úFinds properly ordered node & parent

úReaches the root (reaches node without parent)

siftDown

§Restores heap’s order as last step of remove()

úProcess of restoring order starts at root

úCompare childs' elements to find which more important

úSmaller child element compared with node's element

úSwap when out of order to regain balance in this node

§But method must continue with swapped child

úStop when node has no children (siftDown() hits leaf)

úsiftDown() also stops when elements not unordered

----------------------------------

LinkedHeap

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;
}
}

------------------------------------

*Class that LinkedHeap needs, no need to change*

BTNode

package edu.buffalo.cse116;

public class BTNode {
/** Tree's element which is stored within this Node. */
private E element;

/** Left child of the current Node. */
private BTNode left;
/** Right child of the current Node. */
private BTNode right;
/** Parent in the binary tree for the current Node. */
private BTNode parent;

/**
* Initializes this Entry object. This default constructor is defined for future expansion purposes.
*/
public BTNode() {}

/**
* Initializes this Entry object from element and parent.
*/
public BTNode(E element, BTNode parent) {
this.element = element;
this.parent = parent;
}

/** Return the element stored in this node. */
public E getElement() {
return element;
}

/** Specify a new element to be stored at this node. */
public void setElement(E element) {
this.element = element;
}

/** Get the node's left child. */
public BTNode getLeft() {
return left;
}

/** Specify a node to be the left child of the current node. */
public void setLeft(BTNode left) {
this.left = left;
}

/** Get the node's right child. */
public BTNode getRight() {
return right;
}

/** Specify a node to be the right child of the current node. */
public void setRight(BTNode right) {
this.right = right;
}

/** Get the node's parent in the tree. This is null if the node is a root. */
public BTNode getParent() {
return parent;
}

/** Specify a node to be the parent of the current node. */

public void setParent(BTNode parent) {
this.parent = parent;
}

/** Provides a String representation of the node for use in debugging. */
@Override
public String toString() {
return "BTNode: " + element;
}
}

--------------------

*Class that LinkedHeap needs, no need to change*

BinaryTree

package edu.buffalo.cse116;

import java.util.AbstractCollection;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
* Instances of this class represent a vanilla binary tree (e.g., and not a binary search tree).
*
* @author Matthew Hertz
* @param Type of data stored in each node of this tree. Since this is not a BST, E can be anything.
*/
public class BinaryTree extends AbstractCollection {

/** Root node of this binary tree */
private BTNode root;

/**
* Initializes this BinarySearchTree object to be empty, to contain only elements of type E, to be ordered by the
* Comparable interface, and to contain no duplicate elements.
*/
public BinaryTree() {
root = null;
}

/**
* Returns a reference to the node at the root or null if the tree is empty. This is needed for future uses of a
* linked binary tree.
*
* @return Root node for this tree or null if the tree is empty.
*/
protected BTNode getRootNode() {
return root;
}

/**
* Specifies a new root node for the tree. This is designed to allow future subclasses to make these changes.
*
* @param newRoot The new node to be used as the root for this tree.
*/
protected void setRootNode(BTNode newRoot) {
root = newRoot;
}

/**
* Iterator method that has, at last, been implemented.
*
* @return an iterator positioned at the smallest element in this BinarySearchTree object.
*/
@Override
public Iterator iterator() {
return new TreeIterator();
}

/**
* Determines if there is at least one element in this binary tree object that equals a specified element.
*
* @param obj - the element sought in this binary tree
* @return true if the object is an element in the binary tree; false othrwise.
*/
@Override
public boolean contains(Object obj) {
return getBTNode(obj) != null;
}

/**
* Finds the BTNode object that houses a specified element, if there is such an BTNode.
*
* @param obj - the element whose BTNode is sought.
* @return the BTNode object that houses obj - if there is such an BTNode; otherwise, return null.
*/
protected BTNode getBTNode(Object obj) {
return getBTNode(root, obj);
}

/**
* Finds the BTNode object that houses a specified element in the subtree rooted at subtreeRoot, if there is such an
* BTNode.
*
* @param obj - the element whose BTNode is sought.
* @return the BTNode object that houses obj - if there is such an BTNode in the subtree at subtreeRoot; otherwise,
* return null.
*/
protected BTNode getBTNode(BTNode subtreeRoot, Object obj) {
if (subtreeRoot == null) {
return null;
} else if ((subtreeRoot.getElement() == obj) ||
((subtreeRoot.getElement() != null) && subtreeRoot.getElement().equals(obj))) {
return subtreeRoot;
}
if (subtreeRoot.getLeft() != null) {
BTNode retVal = getBTNode(subtreeRoot.getLeft(), obj);
if (retVal != null) {
return retVal;
}
}
if (subtreeRoot.getRight() != null) {
BTNode retVal = getBTNode(subtreeRoot.getRight(), obj);
if (retVal != null) {
return retVal;
}
}
return null;
}

/**
* Finds the successor of a specified Entry object in this BinarySearchTree. The worstTime(n) is O(n) and
* averageTime(n) is constant.
*
* @param e - the Entry object whose successor is to be found.
* @return the successor of e, if e has a successor; otherwise, return null.
*/
protected BTNode successor(BTNode e) {
if (e == null) {
return null;
} else if (e.getRight() != null) {
// successor is leftmost Entry in right subtree of e
BTNode p = e.getRight();
while (p.getLeft() != null) {
p = p.getLeft();
}
return p;

} // e has a right child
else {

// go up the tree to the left as far as possible, then go up
// to the right.
BTNode p = e.getParent();
BTNode ch = e;
while ((p != null) && (ch == p.getRight())) {
ch = p;
p = p.getParent();
} // while
return p;
} // e has no right child
} // method successor

private class TreeIterator implements Iterator {

private BTNode cursor;

/**
* Positions this TreeIterator to the left-most element in the tree.
*/
public TreeIterator() {
cursor = root;
if (cursor != null) {
while (cursor.getLeft() != null) {
cursor = cursor.getLeft();
}
}
}

/**
* Determines if there are still some elements that have not been accessed by this TreeIterator object.
*
* @return true - if there are still some elements that have not been accessed by this TreeIterator object;
* otherwise, return false.
*/
@Override
public boolean hasNext() {
return cursor != null;
}

/**
* Returns the element in the BTNode this TreeIterator object was positioned at before this call, and advances this
* TreeIterator object.
*
* @return the element this TreeIterator object was positioned at before this call.
* @throws NoSuchElementException - if this TreeIterator object was not positioned at a BTNode before this call.
*/
@Override
public E next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
E retVal = cursor.getElement();
cursor = successor(cursor);
return retVal;
}

/**
* Not implemented.
*/
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}

@Override
public int size() {
throw new UnsupportedOperationException();
}
}

-------------------------

Test code for LinkedHeap

package edu.buffalo.cse116;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNotNull;
import static org.junit.Assert.assertNull;
import static org.junit.Assert.assertTrue;

import java.util.ArrayList;
import java.util.Comparator;

import org.junit.Before;
import org.junit.Test;

/**
* JUnit test cases for your heap class.
*
* @author Matthew Hertz
*/
public class LinkedHeapTest {
/** Values which we will be adding to the list. */
private static final String[] DATA = { "Alpha", "Bravo", "Charlie", "DeltaForce", "Echo", "Foxtrot", "Golf",
"HotelCalifornia" };

/** "Random" ordering in which data is added to the list. */
private static final int[] PRIORITY = { 5, 3, 1, 6, 4, 2, 0, 7 };

/** Ordering in which each element will be removed from the list using our special comparator. */
private static final int[] REMOVAL = { 6, 4, 1, 0, 5, 2, 3, 7 };

/** Dictionary instance we will test. */
private LinkedHeap pq;

/** Setup the heap before each test */
@Before
public void setUp() {
pq = new LinkedHeap<>(new WeirdStringComparator());
}

/**
* Test whether this node obeys the completeness property.
*
* @param node Node we want to check w.r.t. its children.
*/
private void checkHeapCompleteness(BTNode node) {
if (node.getLeft() != null) {
BTNode left = node.getLeft();
if ((left.getLeft() != null) && (left.getRight() != null)) {
assertNotNull("Need to complete one level before starting the next.", node.getRight());
} else if (node.getRight() != null) {
BTNode right = node.getRight();
assertTrue("Need to add nodes from left to right.", (right.getLeft() == null) && (right.getRight() == null));
}
} else {
assertNull("Need to add nodes from left to right!", node.getRight());
}
}

/**
* Test whether this node obeys the heap-order property.
*
* @param node Node we want to check w.r.t. its children.
*/
private void checkLegalBinaryTreeNode(BTNode node) {
String parentEnt = node.getElement();
assertNotNull("Node has null for its element!", parentEnt);
if (node.getLeft() != null) {
String leftEnt = node.getLeft().getElement();
assertNotNull("Oops, left child's element is null.", leftEnt);
assertTrue("Oops. Child (" + leftEnt + ") is smaller than its parent (" + parentEnt + ")!",
(leftEnt.length() >= parentEnt.length()));
}
if (node.getRight() != null) {
String rightEnt = node.getRight().getElement();
assertNotNull("Oops, right child's element is null.", rightEnt);
assertTrue("Oops. Child (" + rightEnt + ") is smaller than its parent (" + parentEnt + ")!",
(rightEnt.length() >= parentEnt.length()));
}
}

/**
* Traverse through all the nodes in the tree and check each for heap order and completeness properties.
*/
private void traverseNodesAndCheck() {
ArrayList> nodeList = new ArrayList<>();
BTNode pos = pq.getRootNode();
nodeList.add(pos);
while (!nodeList.isEmpty()) {
BTNode node = nodeList.remove(0);
checkHeapCompleteness(node);
checkLegalBinaryTreeNode(node);
if (node.getLeft() != null) {
nodeList.add(node.getLeft());
}
if (node.getRight() != null) {
nodeList.add(node.getRight());
}
}
}

@Test
public void testUpHeapWhenEmpty() {
pq.add(DATA[0]);
traverseNodesAndCheck();
}

@Test
public void testChainInsert() {
for (int i = 0; i < DATA.length; i++) {
pq.add(DATA[PRIORITY[i]]);
assertEquals("Not enough nodes in the heap?", i + 1, pq.size());
traverseNodesAndCheck();
}
}

@Test
public void testChainInsertRemoveMin() {
for (int i = 0; i < DATA.length; i++) {
pq.add(DATA[PRIORITY[i]]);
}
for (int i = 0; i < DATA.length; i++) {
String removeEnt = pq.remove();
assertEquals("Did not find the value I expected after " + (i + 1) + " calls to removeMin()", DATA[REMOVAL[i]],
removeEnt);
assertEquals("Incorrect number of nodes after calling removeMin()", DATA.length - (i + 1), pq.size());
if (i != (DATA.length - 1)) {
traverseNodesAndCheck();
}
}
}

private class WeirdStringComparator implements Comparator {

@Override
public int compare(String o1, String o2) {
return (o1.length() - o2.length());
}

}
}

Answer 1

Hi, Please find my implementation.

Please let me know in case of any issue.

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<T> extends BinaryTree<T> {

   /** Stores the last node that we added to this structure. */

   private BTNode<T> lastNode;

   /** Comparator used to organize and order the elements in the heap. */

   private Comparator<T> 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<T> 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<T> node = new BTNode<>();

       node.setElement(obj);

       if (getRootNode() == null) {

           setRootNode(node);

       } else {

           BTNode<T> 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<T> getNextParentAdd() {

       BTNode<T> 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<T> node, T elem) {

       //int p = parent(i);

       // comp - differentiate MaxHeap and MinHeap

       // percolates up

       if((node.getParent()!= null) && comparator.compare(node.getParent().getElement(), node.getElement()) > 0 )

       {

           //Exch(A[i], A[p]);

           T item = node.getParent().getElement();

           node.getParent().setElement(node.getElement());

           node.setElement(item);

           siftUpComparator(node.getParent(), node.getParent().getElement());

       }

   }

   /**

   * 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<T> rootNode = getRootNode();

       T minElement = rootNode.getElement();

       if (size() == 1) {

           setRootNode(null);

           lastNode = null;

       } else {

           BTNode<T> 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;

           //System.out.println("*****"+rootNode.getElement());

           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<T> node, T elem) {

      

       if(node != null)

       {

           System.out.println("parent: "+node.getElement());

           System.out.println("Left: "+node.getLeft().getElement());

           System.out.println("Right: "+node.getRight().getElement());

           BTNode<T> smallest = node;

           if(node.getLeft()!= null && comparator.compare(smallest.getElement(), node.getLeft().getElement()) > 0){

               //System.out.println("Left: "+node.getLeft().getElement());

               smallest = node.getLeft();

           }

           if(node.getRight()!= null && comparator.compare(smallest.getElement(), node.getRight().getElement()) > 0){

               //System.out.println("Right: "+node.getRight().getElement());

               smallest = node.getRight();

           }

           if(smallest != node){

               T item = node.getElement();

               node.setElement(smallest.getElement());

               smallest.setElement(item);

               siftUpComparator(smallest, smallest.getElement());

           }

       }

   }

   /**

   * 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<T> getNewLastNode() {

       BTNode<T> 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<T> rootNode = getRootNode();

       T minElement = rootNode.getElement();

       return minElement;

   }

}