package assignment2;

public class MaxPQ> {

private static int DEFAULT_CAPCITY=10;

// heap-ordered complete binary tree

// in pq[1..N] with pq[0] unused

private Key[] pq;

private int size = 0;

public void insert(Key v) {

pq[++size] = v;

swim(size);

}

public boolean isEmpty() {

return size == 0;

}

public int size() {

return size;

}

public Key max() {

if (size==0) {

return null;

} else {

return pq[1];

}

}

public Key delMax() {

if (size==0) {

return null;

} else {

Key max = pq[1]; // Retrieve max key from top.

swap(1, size--); // Exchange with last item.

pq[size + 1] = null; // Avoid loitering.

sink(1); // Restore heap property.

return max;

}

}

/**

* Change key at index i to newKey and return the old key.

* After this change this priority queue is still a max priority queue

*

* The worst-case running time should not exceed o(lgn),

* and the worst-case space complexity should not exceed O(1),

* where n is the number of elements in the priority queue

*/

public Key change(int i, Key newKey) {

// provide implementation here

return null;

}

// bottom-up repheapify

private void swim(int k) {

while (k > 1 && isLessThan(pq[k/2], pq[k])) {

swap(k/2, k);

k = k/2;

}

}

// top-down repheapify

private void sink(int k) {

while (2*k

int j = 2*k;

if (j

j++; // j is the index of the largest children

if (!isLessThan(pq[k], pq[j]))

break;

swap(k, j);

k = j;

}

}

public MaxPQ() {

this(DEFAULT_CAPCITY);

}

@SuppressWarnings("unchecked")

public MaxPQ(int maxN) {

pq = (Key[]) new Comparable[maxN + 1];

size = 0;

}

@SuppressWarnings("unchecked")

public MaxPQ(Key[] a) {

pq = (Key[]) new Comparable[a.length + 1];

for (int i=0; i

insert(a[i]);

}

}

private void swap(int i, int j) {

Key t = pq[i];

pq[i] = pq[j];

pq[j] = t;

}

private boolean isLessThan(Key v, Key w) {

return v.compareTo(w)

}

Key[] getKeys() {

return pq;

}

}

6. (10 Points) Implement change method inside MaxPQ. Make sure the implementation meet the specified performance requirement. * Change key at index i to newKey and return the old key * After this change this priority queue is still a max priority queue * The worst-case running time should not exceed oCLgn), * and the worst-case space complexity should not exceed 0(1), * where n is the number of elements in the priority queue public Key change(int i, Key newKey) // provide implementation here return null; 6. (10 Points) Implement change method inside MaxPQ. Make sure the implementation meet the specified performance requirement. * Change key at index i to newKey and return the old key * After this change this priority queue is still a max priority queue * The worst-case running time should not exceed oCLgn), * and the worst-case space complexity should not exceed 0(1), * where n is the number of elements in the priority queue public Key change(int i, Key newKey) // provide implementation here return null