Question: Heap Java Programming Assignment Help ________________________________________________ The Project: STAGE 1: using the Heap.java class. Implement the following: 1. Write iterator class for the Heap class.
Heap Java Programming Assignment Help
________________________________________________
The Project:
STAGE 1: using the Heap.java class. Implement the following:
1. Write iterator class for the Heap class. Be sure to include an implementation of the remove operation. (See BST class implementation)
2. Implement a constructor to create a Heap from a given list
public Heap(List aList) {
}
3. Implement a method to add elements of another Heap to this Heap
public void addAll(Heap h) {
}
4. Implement a method to removes elements of another Heap from this Heap
public void removeAll(Heap heap){
}
5. Implement a method that retains only the elements in this Heap that are contained in the specified Heap. In other words, removes from this Heap all of its elements that are not contained in the specified Heap.
public void retainAll(Heap heap){
}
________________________________________________
STAGE 2: Test your class with the following driver program:
TestHeap.java:
public class TestHeap {
/** A test method */
public static void main(String[] args){
Heap l1 = new LinkedHeap<>(Arrays.asList( new Integer[] {5, 10, 12, 14, 16, 20} ));
Heap l2 = new LinkedHeap<>(Arrays.asList( new Integer[] {15, 10, 12, 30} ));
System.out.println(l1);
System.out.println(l2);
l1.addAll(l2);
System.out.println(l1);
l1.removeAll(l2);
System.out.println(l1);
l1 = new LinkedHeap<>(Arrays.asList( new Integer[] {5, 10, 12, 14, 16, 20} ));
l1.retainAll(l2);
System.out.println(l1);
}
}
Output should be:
[20, 14, 16, 5, 12, 10]
[30, 15, 12, 10]
[30, 15, 20, 14, 12, 10, 16, 5, 12, 10]
[20, 14, 16, 5]
[12, 10]
________________________________________________
STAGE 3: Using the Heap.java class. Implement a class called PriorityQueue.
________________________________________________
STAGE 4: Using the PriorityQueue class, write a driver program to find union, difference, and intersection of the following to arrays:
String[] list1 = {"George", "Jim", "John", "Blake", "Kevin", "Michael"};
String[] list2 = {"George", "Katie", "Kevin", "Michelle", "Ryan"};
________________________________________________
Necessary Java files:
Heap.java:
import java.util.*;
public class Heap {
private ArrayList list; // array of list items
private Comparator comparator;
public Heap(){
list = new ArrayList<>();
}
public Heap(T[] anArray){
list = new ArrayList<>();
for(T e : anArray){
add(e);
}
}
public Heap(Comparator comparator){
list = new ArrayList<>();
this.comparator = comparator;
}
// Heap operations
public boolean isEmpty() {
// Check whether a heap is empty
// Precondition: None
// Postcondition: Returns true if the heap is empty
// otherwise return false
return list.isEmpty() ;
}
public void add(T newItem) {
// adds an item into a heap
// Precondition: newItem is the item to be added
// Postcondition: newItem is added in proper location in the heap
// trickle new item up to its proper position
list.add(newItem); // Append to the heap
int currentIndex = list.size() - 1; // The index of the last node
int parentIndex = (currentIndex - 1) / 2;
while (currentIndex >= 0 && (compareItems(list.get(currentIndex), list.get(parentIndex))) > 0 ) {
// Swap list[currentIndex] and list[parentIndex]
T temp = list.get(currentIndex);
list.set(currentIndex, list.get(parentIndex));
list.set(parentIndex, temp);
currentIndex = parentIndex;
parentIndex = (currentIndex - 1) / 2;
} // end while
} // end add
public T remove() {
// Retrieves and deletes the item in the root of a heap
// Precondition: None
// Postcondition: returns item at the root of the heap and deltes it,
// and rebuilds the heap.
// However, if the heap is empty, returns null
T rootItem = null;
int loc;
if (!isEmpty()) {
rootItem = list.get(0);
loc = list.size()-1;
// if we remove the item first, it may make the ArrayList list
// empty, then set() won't work
list.set(0,list.get(loc)); // replace the root with last node
list.remove(loc); // remove the last node
heapRebuild(0); // rebuild the heap from root to a heap
} // end if
return rootItem;
} // end remove
protected void heapRebuild(int root) {
// if the root is not a leaf and the root's search key
// is less than the larger of the search keys in the
// root's children
// index of root's left child, if any
int child = 2 * root + 1;
if (child < list.size() ) {
// root is not a leaf, so it has a left child
// index of root's right child, if any
int rightChild = child + 1;
// if root has a right child, find larger child
if (( rightChild < list.size()) &&
compareItems(list.get(rightChild),list.get(child)) > 0) {
child = rightChild; // index of larger child
}
// if the root's value is smaller than the value in the larger
// child, swap values
if (compareItems(list.get(root),list.get(child)) < 0) {
T temp = list.get(root);
list.set(root,list.get(child));
list.set(child, temp);
// transform the new subtree into a heap
heapRebuild(child);
} // end if
} // end if
// if root is a leaf, do nothing
} // end rebuild
public int compareItems(T item1, T item2){
if (comparator == null) {
return ((Comparable ) item1).compareTo(item2);
}
else {
return comparator.compare(item1, item2);
} // end if
} //end compareItems
public String toString() {
// print the heap
return list.toString();
}
}
________________________________________________
HeapSort.java:
import java.util.*;
import java.util.Comparator;
public class HeapSort {
public static > void heapSort(T[] anArray) {
ArrayList list = new ArrayList();
for (int i=0; i < anArray.length; ++i) {
list.add(anArray[i]);
}
for (int index = list.size()-1; index>=0; --index)
{
heapRebuild(list,index);
}
System.out.println(list);
for(int i = anArray.length - 1; i>=0; i--){
anArray[i] = list.remove(0);
for (int index = list.size()-1; index>=0; --index)
{
heapRebuild(list,index);
}
}
}
protected static > void heapRebuild(ArrayList list,int index) {
// if the root is not a leaf and the root's search key
// is less than the larger of the search keys in the
// root's children
// index of root's left child, if any
int currentIndex = index; // The index of the last node
int parentIndex = (currentIndex - 1) / 2;
if (currentIndex >= 0 && (list.get(currentIndex).compareTo(list.get(parentIndex))) > 0 ) {
// Swap list[currentIndex] and list[parentIndex]
T temp = list.get(currentIndex);
list.set(currentIndex, list.get(parentIndex));
list.set(parentIndex, temp);
currentIndex = parentIndex;
parentIndex = (currentIndex - 1) / 2;
} // end whi
// if root is a leaf, do nothing
} // end rebuild
}
________________________________________________
In case you need it, here is the BST class referenced in number 1:
BST.java:
import java.io.*;
public class BST>
extends AbstractTree {
protected TreeNode root;
protected int size = 0;
/** Create a default binary tree */
public BST() {
}
/** Create a binary tree from an array of objects */
public BST(E[] objects) {
for (int i = 0; i < objects.length; i++)
insert(objects[i]);
}
/** Returns true if the element is in the tree */
public boolean search(E e) {
/* TreeNode current = root; // Start from the root
while (current != null) {
if (e.compareTo(current.element) < 0) {
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
current = current.right;
}
else // element matches current.element
return true; // Element is found
}
return false;*/
return recursiveSearch(root,e);
}
protected boolean recursiveSearch(TreeNode root, E key){
if(root==null){
return false;
}
else if (key.compareTo(root.element)<0){
return recursiveSearch(root.left,key);
}
else if (key.compareTo(root.element)>0) {
return recursiveSearch(root.right,key);
}
else
return true;
}
/** Insert element o into the binary tree
* Return true if the element is inserted successfully */
public boolean insert(E e) {
/* if (root == null)
root = createNewNode(e); // Create a new root
else {
// Locate the parent node
TreeNode parent = null;
TreeNode current = root;
while (current != null)
if (e.compareTo(current.element) < 0) {
parent = current;
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
parent = current;
current = current.right;
}
else
return false; // Duplicate node not inserted
// Create the new node and attach it to the parent node
if (e.compareTo(parent.element) < 0)
parent.left = createNewNode(e);
else
parent.right = createNewNode(e);
}
size++;
return true; // Element inserted
*/
if (this.root == null){
this.root = createNewNode(e);
return true;
}
return recursiveInsert(this.root,e);
}
protected boolean recursiveInsert(TreeNode current, E key)
{
if (key.compareTo(current.element)<0){
if(current.left==null){
current.left = createNewNode(key);
return true;
}
else {
return recursiveInsert(current.left,key);
}
}
else if (key.compareTo(current.element)>0){
if(current.right==null){
current.right = createNewNode(key);
return true;
}
else {
return recursiveInsert(current.right,key);
}
}
else
return true;
}
protected TreeNode createNewNode(E e) {
return new TreeNode(e);
}
/** Inorder traversal from the root*/
public void inorder() {
inorder(root);
}
/** Inorder traversal from a subtree */
protected void inorder(TreeNode root) {
if (root == null)
return;
inorder(root.left);
System.out.print(root.element + " ");
inorder(root.right);
}
/** Postorder traversal from the root */
public void postorder() {
postorder(root);
}
/** Postorder traversal from a subtree */
protected void postorder(TreeNode root) {
if (root == null)
return;
postorder(root.left);
postorder(root.right);
System.out.print(root.element + " ");
}
/** Preorder traversal from the root */
public void preorder() {
preorder(root);
}
/** Preorder traversal from a subtree */
protected void preorder(TreeNode root) {
if (root == null)
return;
System.out.print(root.element + " ");
preorder(root.left);
preorder(root.right);
}
/** Get the number of nodes in the tree */
public int getSize() {
return size;
}
/** Returns the root of the tree */
public TreeNode getRoot() {
return root;
}
/** Returns a path from the root leading to the specified element */
public java.util.ArrayList> path(E e) {
java.util.ArrayList> list =
new java.util.ArrayList>();
TreeNode current = root; // Start from the root
while (current != null) {
list.add(current); // Add the node to the list
if (e.compareTo(current.element) < 0) {
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
current = current.right;
}
else
break;
}
return list; // Return an array of nodes
}
/** Delete an element from the binary tree.
* Return true if the element is deleted successfully
* Return false if the element is not in the tree */
public boolean delete(E e) {
// Locate the node to be deleted and also locate its parent node
TreeNode parent = null;
TreeNode current = root;
while (current != null) {
if (e.compareTo(current.element) < 0) {
parent = current;
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
parent = current;
current = current.right;
}
else
break; // Element is in the tree pointed by current
}
if (current == null)
return false; // Element is not in the tree
// Case 1: current has no left children
if (current.left == null) {
// Connect the parent with the right child of the current node
if (parent == null) {
root = current.right;
}
else {
if (e.compareTo(parent.element) < 0)
parent.left = current.right;
else
parent.right = current.right;
}
}
else {
// Case 2: The current node has a left child
// Locate the rightmost node in the left subtree of
// the current node and also its parent
TreeNode parentOfRightMost = current;
TreeNode rightMost = current.left;
while (rightMost.right != null) {
parentOfRightMost = rightMost;
rightMost = rightMost.right; // Keep going to the right
}
// Replace the element in current by the element in rightMost
current.element = rightMost.element;
// Eliminate rightmost node
if (parentOfRightMost.right == rightMost)
parentOfRightMost.right = rightMost.left;
else
// Special case: parentOfRightMost == current
parentOfRightMost.left = rightMost.left;
}
size--;
return true; // Element inserted
}
/** Obtain an iterator. Use inorder. */
public java.util.Iterator iterator() {
return inorderIterator();
}
/** Obtain an inorder iterator */
public java.util.Iterator inorderIterator() {
return new InorderIterator();
}
// Inner class InorderIterator
class InorderIterator implements java.util.Iterator {
// Store the elements in a list
private java.util.ArrayList list =
new java.util.ArrayList();
private int current = 0; // Point to the current element in list
public InorderIterator() {
inorder(); // Traverse binary tree and store elements in list
}
/** Inorder traversal from the root*/
private void inorder() {
inorder(root);
}
/** Inorder traversal from a subtree */
private void inorder(TreeNode root) {
if (root == null)
return;
inorder(root.left);
list.add(root.element);
inorder(root.right);
}
/** Next element for traversing? */
public boolean hasNext() {
if (current < list.size())
return true;
return false;
}
/** Get the current element and move cursor to the next */
public Object next() {
return list.get(current++);
}
/** Remove the current element and refresh the list */
public void remove() {
delete(list.get(current)); // Delete the current element
list.clear(); // Clear the list
inorder(); // Rebuild the list
}
}
/** Remove all elements from the tree */
public void clear() {
root = null;
size = 0;
}
/** Inner class tree node */
public static class TreeNode> {
E element;
TreeNode left;
TreeNode right;
public TreeNode(E e) {
element = e;
}
}
}
________________________________________________
Thank you to anyone who can help me out!
Step by Step Solution
There are 3 Steps involved in it
1 Expert Approved Answer
Step: 1 Unlock
Question Has Been Solved by an Expert!
Get step-by-step solutions from verified subject matter experts
Step: 2 Unlock
Step: 3 Unlock
Study Help