(Min-heap) The heap presented in the text is also known as a max-heap, in which each node is greater than or equal to any of its children. A min-heap is a heap in which each node is less than or equal to any of its children,. Min-heaps are often used to implement priority queues. Revise the Heap class in Listing 23.9 to implement a min-heap.

Listing 23.9

public class Heap> { private java.util.ArrayList list = new java.util.ArrayList<>(); /** Create a default heap */ public Heap() { } /** Create a heap from an array of objects */ public Heap(E[] objects) { for (int i = 0; i < objects.length; i++) add(objects[i]); } /** Add a new object into the heap */ public void add(E newObject) { list.add(newObject); // Append to the heap int currentIndex = list.size() - 1; // The index of the last node while (currentIndex > 0) { int parentIndex = (currentIndex - 1) / 2; // Swap if the current object is greater than its parent if (list.get(currentIndex).compareTo( list.get(parentIndex)) > 0) { E temp = list.get(currentIndex); list.set(currentIndex, list.get(parentIndex)); list.set(parentIndex, temp); } else break; // the tree is a heap now currentIndex = parentIndex; } } /** Remove the root from the heap */ public E remove() { if (list.size() == 0) return null; E removedObject = list.get(0); list.set(0, list.get(list.size() - 1)); list.remove(list.size() - 1); int currentIndex = 0; while (currentIndex < list.size()) { int leftChildIndex = 2 * currentIndex + 1; int rightChildIndex = 2 * currentIndex + 2; // Find the maximum between two children if (leftChildIndex >= list.size()) break; // The tree is a heap int maxIndex = leftChildIndex; if (rightChildIndex < list.size()) { if (list.get(maxIndex).compareTo( list.get(rightChildIndex)) < 0) { maxIndex = rightChildIndex; } } // Swap if the current node is less than the maximum if (list.get(currentIndex).compareTo( list.get(maxIndex)) < 0) { E temp = list.get(maxIndex); list.set(maxIndex, list.get(currentIndex)); list.set(currentIndex, temp); currentIndex = maxIndex; } else break; // The tree is a heap } return removedObject; } /** Get the number of nodes in the tree */ public int getSize() { return list.size(); } /** Return true if heap is empty */ public boolean isEmpty() { return list.size() == 0; } }

Write a program to test the Min-heap. The main method will:

Create an array of Integers that contains the Integers 1 through 9, in unsorted order and print out the values in the array

Create a Min-heap from this array of unsorted Integers and print out the values by repeatedly removing the root Integer from the Min-heap and printing out its value

Create a Min-heap of Strings that contains Strings in unsorted order and print out the values in the array

Create a Min-heap from this array of unsorted Strings and print out the values by repeatedly removing the root String from the Min-heap and printing out its value

Your output should match the sample below:

Unsorted Integers in the array:

8 9 2 3 4 1 5 6 7

Sorted Integers:

1 2 3 4 5 6 7 8 9

Unsorted Strings in the array:

Computer Science Rocks

Sorted Strings:

Computer Rocks Science