Question: Parts of an array backed binary minimum heap have been implemented for you. Complete the implementation by implementing the following functions in java: swim(...) removeMin(...)
Parts of an array backed binary minimum heap have been implemented for you. Complete the implementation by implementing the following functions in java:
- swim(...)
- removeMin(...)
- insert(...)
- sink(...)
public class MinHeap> implements Iterable {
protected final int initialCapacity = 10;
private int size = 0;
protected T[] array = (T[])Array.newInstance(Comparable.class, initialCapacity + 1);
public int size() {
return size;
}
public int maxsize() {
return array.length - 1;
}
public boolean isEmpty() {
return size() == 0;
}
private int isparent(int index) {
return index / 2;
}
private int isleft(int index) {
return 2 * index;
}
private int isright(int index) {
return 2 * index + 1;
}
private void change(int i, int j) {
T temp = array[i];
array[i] = array[j];
array[j] = temp;
}
private boolean less(T v, T w) {
return v.compareTo(w) < 0;
}
private boolean isLeaf(int i) {
if (right(i) >= size || left(i) >= size) {
return true;
}
return false;
}
/** Resize this container's backing array to the new capacity */
private void resize(int maxsize) {
T[] tmp = (T[]) Array.newInstance(Comparable.class,capacity);
System.arraycopy(array, 1, tmp, 1, size);
array = tmp;
}
public T min() {
if (isEmpty()) {
throw new NoSuchElementException("Priority queue underflow");
}
return array[1];
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
