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

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!