You are not allowed to use any JAVA API List Classes.

#Write a program in Java to implement a d-heap data structure that supports the following operations:

1) deleteMin (and percolate down)

2) insert

3) buildHeap

The value of 'd' is input by the user. A sample inputis given below.

Enter heap elements: 31 16 24 21 13

Enter d: 2

Output: Heap (d=2): 13 16 24 31 21

Press 1) for insert, 2) for deleteMin, 3) for new d value, 4) to quit

Enter choice: 1

Enter element to insert: 6

Output: Heap (d=2): 6 16 13 31 21 24

Press 1) for insert, 2) for deleteMin, 3) for new d value, 4) to quit

Enter choice: 1

Enter element to insert: 20

Output: Heap (d=2): 6 16 13 31 21 24 20

Press 1) for insert, 2) for deleteMin, 3) for new d value, 4) to quit

Enter choice: 2 Output: Heap (d=2): 13 16 20 31 21 24

Enter choice: 3

Enter d: 3

Output: Heap (d=3): 13 16 20 31 21 24

Press 1) for insert, 2) for deleteMin, 3) for new d value, 4) to quit

Enter choice: 3

Enter d: 4

Output: Heap with d=4: 13 16 20 31 21 24

Press 1) for insert, 2) for deleteMin, 3) for new d value, 4) to quit

Enter choice: 4

Program Terminated

Your program will be tested with a larger heap with more elements and different d values.

#Question 2. One of the main applications of a heap is to maintain a prioritized queue such as the job queue at a printer.

Although in most job queues, removing the job with the highest priority (deleteMin) and inserting a new job (insert) are the two main operations, there are two other operations that are used alongside. The first one is to remove a job with a given priority or key from the priority queue, the second one is to change the priority of a certain job to a new priority. In this question, you will extend the basic binary heap with these two new operations that are given below:

remove(x) removes the key x from the heap changeValue(x, xnew) changes the value of key x to xnew

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. As before, we will use only integer keys for all operations. Your program should accept a 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 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.