Required files: MinHeap.java and Test.java

Implement of the MinHeap class The ADT of the MinHeap class is given below:

public class MinHeap extends AbstractPQueue { private ArrayList list = new ArrayList();; //constructor public int size(); public boolean isEmpty(); public void heapUp(int i); public void heapDown(int i); public PQEntry insert(Integer key, String value); public PQEntry removeMin(); public PQEntry min(); } 

Requirements:

Implement the MinHeap classes as we discussed in the lectures.

Your implementation has to follow the specification given. Any other implementation (there are tons of MinHeap code on the Internet) will not receive any credit.

Test: write a performance test program to measure the performance of the Heap class in running time. To do that, you may want to construct a big MinHeap with a big number of elements in your test program, such as 1,000. For example, you may set their key values from 1 to 10,000 ( the values can be random numbers, which really does not matter). Our test program should print out the time consumption to remove 1,000 elements.

public class MinHeap extends AbstractPQueue { private ArrayList list = new ArrayList();; //constructor public int size(); public boolean isEmpty(); public void heapUp(int i); public void heapDown(int i); public PQEntry insert(Integer key, String value); public PQEntry removeMin(); public PQEntry min(); }

public void heapup (int i) { while (i>0) do { p<---parent(i); if(key(i)>=key(p) break; swap(i,k) i<---k; } }

public void heapdown (int i) { while (hasleft(i)) { leftindex<---left(i); smallchildindex<---leftindex; if (hasright(i)) { rightindex = right(i); if (key(leftindex > key(rightindex) smallchildindex = rightindex;; }

if (key(i)) <= key(smallchildindex)) break; swap(i, smallchildindex); }

public PQEntry insert (integer key, String value) { heap add (heap.size(), newest); heapup(heap.size()-1); return newestl }

public PQEntry removeMin() { if (heap isEmpty()) return null; swap (0, heap.size() - 1); answer <--- heap.remove(heapsize() - 1); heapdown(0); return answer; }