Please do this in Java programming language

The purpose of this assignment is to implement a binary heap-based priority queue, apply it to implement a heapsort array-sorting algorithm, and to compare the performance of that heapsort to the performance achievable with the sorting methods that are already available in Java. You are also encouraged to compare your priority queue performance to the one in the java.util package! Introduction In this assignment you will implement a class that extends an AbstractQueue class, which in itself implements a Queue interface. Note that each of the queue methods exists in two version: a version returning a special value, and a version that throws an exception. Like with any queue implementation utilizing a binary heap data structure, the performance of insertions and removals is going to be O(log n), while examining the value will be done in constant time. While there are other data structures that are more efficient in theory, real-world performance of binary heaps is often superior, especially when no additional functionality is required (e.g., changing the keys). Implementation Your implementation should use an array representation of the binary heap. In addition, you should not use the first position of the array The array should also grow automatically, as needed (similar to how it's implemented in ArrayList, for example). Automatic shrinking is not required. Part 1 Implement the following public methods: 1. boolean offer(E e) 2. boolean add(E e) 3. E poll() 4. E remove() 5. E peek() 6. E element) 7. int size() 8. String toString() (described below) 9. String toTree() (described below) One public constructor should exist in your implementation: the one that takes no parameters and creates an empty queue when the class is instantiated. No other methods need to be implemented or overridden (e.g., the iterator() method is not required). The behaviour of the methods in your implementation should be equivalent to that of Java Standard Library's classes (i.e., java.util.PriorityQueue; please refer to the class API online) toString() should simply return a String with the contents of the array: [null, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] The array looks sorted, as the items were inserted sequentially, from 1 to 12. When the same are inserted in the reverse order, the resulting array will be: [null, 1, 3, 2, 6, 4, 7, 8, 12, 9, 10, 5, 11] toTree() method should return a String with the tree representation of the heap, as follows, for the same two examples. 1 3 2 5 10 11 6 4 9 7 8 12 1 3 2 4 7 8 6 9 12 10 5 11 Of course, you are free to implement any private or protected methods and classes as you see fit. However, you should not have any public methods other than the ones mentioned (or the ones present in the interface or in the class' superclass). Part 2 Name your class PQSort and put it in the default package. Inside, create the following two public methods: static > void heapSort(E[] a) static > void heapSort2011(E[] a) Both of these methods should implement a heap sort algorithm using priority queues (not-in-place kind). The first method should rely on the java.util.PriorityQueue implementation, and the second one - - on the priority queue you implemented in Part 1. NB: These methods can literally be implemented in three lines each. Test the methods to ensure they work correctly (and produce the same result). The order is non-decreasing. Part 3 Create some tester class and use it with your queue implementation to investigate its running time complexity as the number of items you insert in the queue increases. Try using values from 10 to 1,000,000 while measuring the running time. Confirm that the running time follows the expected logarithmic behaviour for both add and remove methods. The purpose of this assignment is to implement a binary heap-based priority queue, apply it to implement a heapsort array-sorting algorithm, and to compare the performance of that heapsort to the performance achievable with the sorting methods that are already available in Java. You are also encouraged to compare your priority queue performance to the one in the java.util package! Introduction In this assignment you will implement a class that extends an AbstractQueue class, which in itself implements a Queue interface. Note that each of the queue methods exists in two version: a version returning a special value, and a version that throws an exception. Like with any queue implementation utilizing a binary heap data structure, the performance of insertions and removals is going to be O(log n), while examining the value will be done in constant time. While there are other data structures that are more efficient in theory, real-world performance of binary heaps is often superior, especially when no additional functionality is required (e.g., changing the keys). Implementation Your implementation should use an array representation of the binary heap. In addition, you should not use the first position of the array The array should also grow automatically, as needed (similar to how it's implemented in ArrayList, for example). Automatic shrinking is not required. Part 1 Implement the following public methods: 1. boolean offer(E e) 2. boolean add(E e) 3. E poll() 4. E remove() 5. E peek() 6. E element) 7. int size() 8. String toString() (described below) 9. String toTree() (described below) One public constructor should exist in your implementation: the one that takes no parameters and creates an empty queue when the class is instantiated. No other methods need to be implemented or overridden (e.g., the iterator() method is not required). The behaviour of the methods in your implementation should be equivalent to that of Java Standard Library's classes (i.e., java.util.PriorityQueue; please refer to the class API online) toString() should simply return a String with the contents of the array: [null, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] The array looks sorted, as the items were inserted sequentially, from 1 to 12. When the same are inserted in the reverse order, the resulting array will be: [null, 1, 3, 2, 6, 4, 7, 8, 12, 9, 10, 5, 11] toTree() method should return a String with the tree representation of the heap, as follows, for the same two examples. 1 3 2 5 10 11 6 4 9 7 8 12 1 3 2 4 7 8 6 9 12 10 5 11 Of course, you are free to implement any private or protected methods and classes as you see fit. However, you should not have any public methods other than the ones mentioned (or the ones present in the interface or in the class' superclass). Part 2 Name your class PQSort and put it in the default package. Inside, create the following two public methods: static > void heapSort(E[] a) static > void heapSort2011(E[] a) Both of these methods should implement a heap sort algorithm using priority queues (not-in-place kind). The first method should rely on the java.util.PriorityQueue implementation, and the second one - - on the priority queue you implemented in Part 1. NB: These methods can literally be implemented in three lines each. Test the methods to ensure they work correctly (and produce the same result). The order is non-decreasing. Part 3 Create some tester class and use it with your queue implementation to investigate its running time complexity as the number of items you insert in the queue increases. Try using values from 10 to 1,000,000 while measuring the running time. Confirm that the running time follows the expected logarithmic behaviour for both add and remove methods