Since we do not want to have to rewrite this code when the element type changes,
ID: 3834912 • Letter: S
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.
----------------------------------
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 <T> 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) {
}
/**
* 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;
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) {
}
/**
* 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;
}
}
------------------------------------
*Class that LinkedHeap needs, no need to change*
BTNode
package edu.buffalo.cse116;
public class BTNode<E> {
/** Tree's element which is stored within this Node. */
private E element;
/** Left child of the current Node. */
private BTNode<E> left;
/** Right child of the current Node. */
private BTNode<E> right;
/** Parent in the binary tree for the current Node. */
private BTNode<E> 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<E> 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<E> getLeft() {
return left;
}
/** Specify a node to be the left child of the current node. */
public void setLeft(BTNode<E> left) {
this.left = left;
}
/** Get the node's right child. */
public BTNode<E> getRight() {
return right;
}
/** Specify a node to be the right child of the current node. */
public void setRight(BTNode<E> right) {
this.right = right;
}
/** Get the node's parent in the tree. This is null if the node is a root. */
public BTNode<E> getParent() {
return parent;
}
/** Specify a node to be the parent of the current node. */
public void setParent(BTNode<E> 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 <E> Type of data stored in each node of this tree. Since this is not a BST, E can be anything.
*/
public class BinaryTree<E> extends AbstractCollection<E> {
/** Root node of this binary tree */
private BTNode<E> 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<E> 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<E> 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<E> 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<E> 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<E> getBTNode(BTNode<E> 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<E> retVal = getBTNode(subtreeRoot.getLeft(), obj);
if (retVal != null) {
return retVal;
}
}
if (subtreeRoot.getRight() != null) {
BTNode<E> 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<E> successor(BTNode<E> e) {
if (e == null) {
return null;
} else if (e.getRight() != null) {
// successor is leftmost Entry in right subtree of e
BTNode<E> 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<E> p = e.getParent();
BTNode<E> 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<E> {
private BTNode<E> 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<String> 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<String> node) {
if (node.getLeft() != null) {
BTNode<String> 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<String> 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<String> 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<BTNode<String>> nodeList = new ArrayList<>();
BTNode<String> pos = pq.getRootNode();
nodeList.add(pos);
while (!nodeList.isEmpty()) {
BTNode<String> 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<String> {
@Override
public int compare(String o1, String o2) {
return (o1.length() - o2.length());
}
}
}
Explanation / Answer
public class LinkedHeap
{
int[] lH;
public BinaryHeap(int M)
{
lH = new int[M + 1];
}
int N = 1;
public void put(int key)
{
lH[this.k] = key;
if(lH[this.n] > lH[this.n/2])
{
swim(this.n);
}
this.n++;
}
public void deleteMax()
{
lH[1] = lH[n];
sink(1);
this.n--;
}
public void deleteMin()
{
lH[this.n - 1] = 0;
this.n--;
}
public void swim(int n)
{
while((k != 1) && (lH[n] > lH[n/2]))
{
swap(n, n/2);
n = n/2;
}
}
public void sink(int n)
{
while(2*n <= this.n)
{
int j = 2*n;
if(max(j, j+1)) j++;
if(lH[n] < lH[j])
swap(n, j);
else if(lH[n] > lH[j])
break;
n = j;
}
}
private boolean max(int i, int j)
{
if(lH[i] < lH[j])
return true;
return false;
}
private void swap(int i, int j)
{
int temp = 0;
temp = lH[i];
lH[i] = lH[j];
lH[j] = temp;
}
private void printAll()
{
for(int i=1; i < this.k; i++)
{
System.out.print(lH[i] + " ");
}
System.out.println();
}
public static void main(String[] args) throws Exception
{
int a[] = {5,8,7,9,2,9,3,7};
BinaryHeap bh = new BinaryHeap(a.length);
for(int i=0; i < a.length; i++)
{
bh.put(a[i]);
}
System.out.println("Elements in Linked Heap: ");
bh.printAll();
System.out.println("Del Minimum: ");
bh.deleteMin();
bh.printAll();
System.out.println("Del Maximum: ");
bh.deleteMax();
bh.printAll();
}
}