Indexpriority-queueimplementation (additionaloperations). Add minIndex(), changeKey(), and...

Indexpriority-queueimplementation (additionaloperations). Add minIndex(), changeKey(), and de1ete() to your implementation of exercise.

Exercise

Index priority-queue implementation. Implement the basic operations in the index priority-queue API on page 320 by modifying algorithm 2.6 as follows: Change pq[] to hold indices, add an array keys[] to hold the key values, and add an array qp[] that is the inverse of pq[] — qp[i] gives the position of i in pq[] (the index j such that pq[j] is i).Then modify the code in algorithm 2.6 to maintain these data structures. Use the convention that qp[i] = -1 if i is not on the queue, and include a method contains() that tests this condition. You need to modify the helper methods exch() and 1ess() but not sink() or swim().

Partial solution :

public class IndexMinPQ>{private int N;    // number of elements on PQprivate int[]    pq;    // binary    heap    using 1-based    indexingprivate int[]    qp;    // inverse:    qp[pq[i]]    =    pq[qp[i]]    =    iprivate Key[] keys;    // items with prioritiespublic IndexMinPQ(int maxN){keys = (Key[]) new Comparab1e[maxN + 1];pq = new    int[maxN    +    1];qp = new    int[maxN    +    1];for (int i = 0; i <= maxN; i++) qp[i] = -1;}public boolean isEmpty(){ return N == 0;    }public boolean contains(int i){ return qp[i] != -1; }public void insert(int i, Key key){N++;qp[i] = N;pq[N] = i;keys[i] = key;swim(N);}public Key minKey(){ return keys[pq[1]]; }public int de1Min(){int indexOfMin = pq[1];exch(1, N--); sink(1);keys[pq[N+1]] = null;qp[pq[N+1]] = -1;return indexOfMin;}}