Introduction In this assignment you will implement a class that extends an AbstractQueue class, which in itself implements a Queue interface. Note that the names of the methods in that interface differ from the ones used for priority queues in the textbook. Also 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). In addition to the lecture notes, you might find the following resources useful: Priority Queues chapter of the Algorithms textbook https://algs4.cs.princeton.edu/24pq/ Implementation Name your class PriorityQueue 2011 and put it in the default package. Your implementation should use an array representation of the binary heap. In addition, you should not use the first position of the array, just like described in the link above. The array should also grow automatically, as needed (similar to how it's implemented in ArrayList, for example). Automatic shrinking is not required. 6. E 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() 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 2 3 5 6 7 8 9 10 11 12 4 N 1 3 6 4 9 10 5 11 7 8 12 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 heapSort 2011(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. Introduction In this assignment you will implement a class that extends an AbstractQueue class, which in itself implements a Queue interface. Note that the names of the methods in that interface differ from the ones used for priority queues in the textbook. Also 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). In addition to the lecture notes, you might find the following resources useful: Priority Queues chapter of the Algorithms textbook https://algs4.cs.princeton.edu/24pq/ Implementation Name your class PriorityQueue 2011 and put it in the default package. Your implementation should use an array representation of the binary heap. In addition, you should not use the first position of the array, just like described in the link above. The array should also grow automatically, as needed (similar to how it's implemented in ArrayList, for example). Automatic shrinking is not required. 6. E 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() 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 2 3 5 6 7 8 9 10 11 12 4 N 1 3 6 4 9 10 5 11 7 8 12 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 heapSort 2011(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