Submit this completed document along with a .zip of your entire project. You should use a heap as part of your implementation of parts 1-3. The driver should use the classes you created. Carefully consider your implementation – use the properties of heaps to make your code more efficient.

1. (30%) Create a class in the jsjf package called HeapStack that implements the StackADT interface from earlier this semester using the ArrayHeap or LinkedHeap implementation from the Java Foundations book. Keep in mind that a stack is a LIFO structure. Thus, the comparison in the heap will have to be according to order entry into the stack. You must use a heap to implement the StackADT interface.
2. (20%) Create a class in the jsjf package called HeapQueue that implements the QueueADT interface from earlier this semester using theArrayHeap or LinkedHeap implementation from the Java Foundations book. You must use a heap to implement the QueueADT interface.
3. (30%) Create a method in the Sorting class called smallestN that takes an array of Comparable objects and an integer as parameters and returns an ArrayList with the smallest N elements in the array. You must use a heap to implement this method to receive credit.
4. (20%) Create a driver called HeapDriver.java to test your implementation. Your driver should do the following:
   a. Create an array of String objects that contains the words of the sentence “This is my heaps project for CSC205”
   b. Print the smallest 4 elements of the array (using your smallestN method)
   c. Create the following data structures:
   ● a min heap
   ● a HeapStack
   ● a HeapQueue
   and add the contents of the Comparable array you created in part A to each of them. (Note that this will test that your smallestN method does not change the input array!)
   d. Removeall the words from each data structure in part c, printing them on a single line in the order they are removed.

You should reuse or modify the example methods from class where appropriate. Do not use any Java library methods. Unnecessarily duplicating existing code or failing to use the properties of heaps to make your code more efficient will result in a grade of 0 for that method. Feel free to implement helper methods or additional classes where appropriate, but if you do so include those methods/classes in your submission. A minimum of 10 points will be deducted for any missing/incorrect submission information. Be prepared to discuss your project in class following the due date.

Briefly describe your implementation & any issues you ran into (if any) in the box below:

Copy the output of your driver as text in the box below:

For the following, if you implemented a method with multiple methods, include all the methods you wrote that are called by that method.
Copy your entire HeapStack class as text in the box below:

Copy your enqueue method as text in the box below:

Copy your dequeue method as text in the box below:

Copy your smallestN method as text in the box below:

Copy your driver class as text in the box below: