public class MaxPQ<Key extends Comparable<Key>> { private static int DEFAULT_CAP
ID: 3722663 • Letter: P
Question
public class MaxPQ<Key extends Comparable<Key>> {
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 <= size) {
int j = 2*k;
if (j < size && isLessThan(pq[j], pq[j + 1]))
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<a.length; 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) < 0;
}
Key[] getKeys() {
return pq;
}
}
Explanation / Answer
public class MaxPQ<Key extends Comparable<Key>> {
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
//Get the Old Key
Key oldKey = pq[i];
//Replce it with nEWkEY
pq[i] = newKey;
//HeapIfy at index i that takes log n time
sink(i);
//return oldKey
return oldKey;
}
// 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 <= size) {
int j = 2*k;
if (j < size && isLessThan(pq[j], pq[j + 1]))
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<a.length; 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) < 0;
}
Key[] getKeys() {
return pq;
}
}
=====================================================
Thanks, let me know if there is any doubts/concern.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.