STAGE 1: using the Heap.java class. Implement the following:

Write iterator class for the Heap class. Be sure to include an implementation of the remove operation. (See BST class implementation)

Implement a constructor to create a Heap from a given list

public Heap(List aList) {

}

Implement a method to add elements of another Heap to this Heap

public void addAll(Heap h) {

}

Implement a method to removes elements of another Heap from this Heap

public void removeAll(Heap heap){

}

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:

public class TestHeap {

/** A test method */

public static void main(String[] args){

LinkedHeap l1 = new LinkedHeap<>(Arrays.asList(

new Integer[] {5, 10, 12, 14, 16, 20} ));

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

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 }