The main objective of this assignment is to familiar yourself with several important operations related to heaps (priority queues). Just like the previous two programming assignments, this assignment is about binary trees. However, unlike the previous two, binary heap is a complete binary tree but not a binary search tree, and is implemented using arrays (rather than pointers) due to its structure property.In this programming assignment, you will extend the basic binary heap with these two new operations that are given below: remove(x) removes the key with value x (not the key at index x) from the heap. In case the value is not found, a message the value, x, is not found) should be displayed (instead of printing the remaining contents in the array, as in the normal case). changeValue(x, xnew) changes the value of key x to xnew. Again, x refers to a value, not an index. And again, in case the x is not in the heap, a message should be displayed rather than printing the updated heap content (as in the normal case). For implementing these operations you have to use the percolateUp and percolateDown techniques, along with appropriate additional logic. If you use any other technique to implement the operations, you will not get full points. Write a program in Java that implements the binary heap with the remove and changeValue operations along with the basic operations of insert, deleteMin and buildHeap. You can reuse the code for the basic operations and the code for the binary heap data structure from the textbooks code repository. As before, we will use only integer keys for all operations. Your program should accept a comma separated list of integers as input from console. After input is done, your program should show a menu interface. The basic heap operations required in the question, like insert, buildHeap and deleteMin should be a menu entry each. Plus you need to have menu entries for the two operations you are implementing in the question, and, exit. In summary, your completed program should provide a simple user interface (as previous programming assignments) with the following 7 options. Note that comments for the entire program as well as for each method/function are required as usual. In addition, since remove(x) and changeValue(x, xnew) are two new methods developed by yourself, you should briefly describe the underlying algorithm before the actual code is presented. Failing to provide such comments is subject to point deduction (up to 1/3 of points allocated to these methods), even the operation works correctly.

1. buildheap You must use the linear algorithm. Starting with an empty array, takes up to 20 integers as input

2. insert (using percolate up), then print (use option 6).

3. deleteMin (using percolate down), then print (use option 6).

4. remove(x) removes the key with value x (not the key at index x) from the heap, then print (use option 6).

5. changeValue(x, xnew) -- changes the value of key x to xnew (again, x is an actual value, not an index), then print (use option 6).

6. Print Starting with a message The heap has the following elements:, it prints the current contents in the array. In addition to a standalone option, print method should always be called as the last step of any option 1 to 5.

7. Exit

(1) As usual, remember to create a folder in your home directory named using the convention stated before. The name of the submission directory on Loki should be CSCI-3320-ZC-S20-PA4A (or PA4B) depending on which section you are in.

(2) In addition to the completed .java file, you should also submit a typed report which should contains two parts:

(i) A brief description on how your remove (option 4) and changeValues (option 5) operations work. You should not simply copy your java code. Instead you should use English sentences or pseudocode to explain how these operations work, and manually execute option 4 and option 5 using the testing data shown below (just like a written assignment). Your answers should be in tree format (instead of in array format). Without a complete answer of this part, your program will not be graded.

(ii) As in previous programming assignments, you should also submit a sample execution of your completed program. You should execute your program EXACTLY using the steps as described below, copy and paste the screen shots to a word file, and submit this file along with the java file in the folder as described above. Here are the following options to be used to demonstrate your program (do NOT change the order of steps):

Select option 1 to build a heap using the following input sequence: 35, 98, 17, 27, 46, 82, 75, 68, 5, 3, 19, 22, 43, 9, 2.

Select option 3 deleteMin.

Select option 4, remove 17.

Select option 5, change 5 to 12.

Select option 5, change 19 to 4.

Select option 2, insert 1.

Select option 4, remove 5.

Select option 6.

Select option 7.

Chapter 5 Hashing private int myhash( AnyType x ) { int hashVal = x.hashCode(); 1 2 3 4. 5 6 hashVal %= theLists.length; if( hashVal (); 18 } 19 20 21 * Make the hash table logically empty. 22 */ 23 public void makeEmpty ( ) 24 { 25 for(int i = 0; i whichList = theLists [ myhash( x ) ); return whichList.contains ( x ): } 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 /** * Insert into the hash table. If the item is * already present, then do nothing. * @param x the item to insert. */ public void insert( Any Type x ) { List whichList = theLists [ myhash( x ) ]; if( !whichList.contains ( x ) ) { whichList.add( x ); // Rehash; see Section 5.5 if( +-currentSize > thelists.length ) rehash(); } } * Remove from the hash table. * @param x the item to remove. 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 public void remove( AnyType x ) { List whichList = theLists [ myhash(x) ; if( whichList.contains( x ) ) { whichList.remove( x ); currentSize--; Figure 5.10 contains, insert, and remove routines for separate chaining hash table Chapter 5 Hashing private int myhash( AnyType x ) { int hashVal = x.hashCode(); 1 2 3 4. 5 6 hashVal %= theLists.length; if( hashVal (); 18 } 19 20 21 * Make the hash table logically empty. 22 */ 23 public void makeEmpty ( ) 24 { 25 for(int i = 0; i whichList = theLists [ myhash( x ) ); return whichList.contains ( x ): } 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 /** * Insert into the hash table. If the item is * already present, then do nothing. * @param x the item to insert. */ public void insert( Any Type x ) { List whichList = theLists [ myhash( x ) ]; if( !whichList.contains ( x ) ) { whichList.add( x ); // Rehash; see Section 5.5 if( +-currentSize > thelists.length ) rehash(); } } * Remove from the hash table. * @param x the item to remove. 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 public void remove( AnyType x ) { List whichList = theLists [ myhash(x) ; if( whichList.contains( x ) ) { whichList.remove( x ); currentSize--; Figure 5.10 contains, insert, and remove routines for separate chaining hash table