CSC 17 Priority Heap Lab This lab will serve several purposes: a. understand and use the heap data structure b. understand the time complexity of heap algorithms. c. use inheritance to improve a Heap implementation. Download my Heap25.java and HeapDisplay.java programs. https://cs.hofstra.edu/~cscccl/csc17/Heap25.java https://cs.hofstra.edu/~cscccl/csc17/HeapDisplay.java All your code for this lab should be in a separate file myheap.java with a class. Compile your program together with the two you downloaded: javac myheap.java Heap.java HeapDisplay.java To use the heapdisplay program, you can add the following method to your subclass of Heap (never edit the Heap superclass itself - you'll "void the warrantee"): Call drawheap will pop up a window and draw the heap graphically. YOU ARE NOT ALLOWED TO EDIT Heap25.java, all changes you wish to make must be made in the subclass. public class myheap> extends Heap25 { // constructors of the subclass should be written this way: public myheap(int cap) { super(cap); } public myheap(int cap, Comparator c) { super(cap,c); } public myheap(T[] A, int size, Comparator c) { super(A,size,c); } public void drawheap() // use only with HeapDisplay.java program { HeapDisplay W = new HeapDisplay(1024,768); W.drawtree(H,size); } // ... other methods (see below) // create a main to test } Part 1: Add the following additional operations to your heap class: a. public Optional push_n_pop(T x) This operation should at once take the top value from the heap and exchange it with x, then swapdown on x until it's in place. This is faster than first popping then pushing separately. b. public void pop_n_swap() This operation should do the same thing as pop, except, instead of returning the popped value, it should swap it to the end of the heap. That is, swap the value at H[0] with H[size-1], then call swapdown(0). This function will be useful later. c. public Heap merge(Heap other) This function should create a new heap that merges this heap with the other heap. The capacity of the new heap should be twice as large as the heap with the larger capacity. Use the heapify algorithm. Part 2: We can use the basic characteristics of a heap to implement a sorting algorithm as follows: 1. Given an array A of comparable objects, insert the elements into a maxheap. 2. Now, reconstruct the A array (backwards) by deleting the maximum (top) element from the heap one by one. That is write a loop that starts at the last index of the array: for(int i=A.length-1;i>=0;i--)... This algorithm runs in (worst-case) O(n*log n) time since you need to perform n push operations and each push takes worst-case log(n) time. You then perform n pop operations, each also taking log(n) time, which givens you 2*n*log(n) steps. Implement this sorting algorithm. You can implement this algorithm as an independent polymorphic function: // sorts array A public static > void heapsort(S[] A) // this funciton is independently polymorphic (parameterized by ) { // outline: // 1.create a Heap HA with capacity same as A.length // 2.insert every value in A into HA // 3.use a backwards loop to fill array with HA.pop_unchecked() values } Test your algorithm with random data: int n = 100000; // sort 100K numbers Integer[] A = new Integer[n]; for(int i=0;iA[i+1]) System.out.println("OOPS"); // shouldn't print this Part 2b: The sorting algorithm of part 2 uses twice as much memory because the array representing the heap is different from the array to be sorted. You need to write a new version of heapsort (heapsort2) that correct this problem. You can use the heapify algorithm to first transform your array into a heap, then call your pop_n_swap function n times to sort the heap. Write a heapsort2 function that uses this technique. Part 3: Unlike insert and delete, searching for an element in a heap is still worst-case O(n) and not O(log n). There's a simple search algorithm in the superclass. This algorithm just searches the underlining array H for x. It does not take any advantage of the structure of the heap. For example, if the top element of the heap is 5 and we're searching for 6, we can immediately conclude that it's not in the tree. In general, if x is larger than the number at a certain node in the tree, then we know that it cannot be in the "subtree" beneath that node. You need to implement a better search algorithm that takes advantage of this fact. The algorithm will still be worst case O(n) but will be faster than the naive algorithm above. Your new search function will @Override the superclass version. A few hints about this problem: 1. Don't think of the structure as an array but as a tree. 2. Think recursively: what does it MEAN for a number to be in a heap: it can be equal to the root, or if it's less than the root, it could in the left subtree or in the right subtree. The base case of the induction is either when you've found what you're looking for, or when you can conclude that the value can't possibly be in the tree (either because you're at the end of the tree or that the value you're looking for is greater than the root of the subtree). 3. You should write an auxiliary function that takes an additional parameter, such as the current index of the node that you're searching at. Then your main function should just call the auxiliary function with the additional parameter set to 0. (start with 0 the root). 4. I can write this program using a single return statement: return ... && ... && (... || ... || ...); You can take 3 or 4 lines but anything much longer would be wrong.