We have 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. We have to implement a class that extends an AbstractQueue class, which in itself implements a Queue interface. Also note that each of the queue methods exists in two versions: a version returning a special value, and a version that throws an exception. Name your class PriorityQueue2011 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. The array should also grow automatically, as needed (similar to how its implemented in ArrayList, for example). Automatic shrinking is not required.
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 2 3 4 5 6 8 9 10 11 12 N 7 1 3 2 3 6 7 12 910 5 11 4 8 The following reference might be useful: https://docs.oracle.com/javase/tutorial/essential/io/formatting.html 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). 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 2 3 4 5 6 8 9 10 11 12 N 7 1 3 2 3 6 7 12 910 5 11 4 8 The following reference might be useful: https://docs.oracle.com/javase/tutorial/essential/io/formatting.html 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)
