Question: Need a driver program to make this class run. driver class should be named as Test.java. MinHeap.java import java.util.ArrayList; public class MinHeap extends AbstractPQueue {
Need a driver program to make this class run. driver class should be named as Test.java.
MinHeap.java
import java.util.ArrayList;
public class MinHeap extends AbstractPQueue {
private ArrayList list = new ArrayList();
MinHeap heap;
// constructor
int parent(int i) {
return (i-1)/2;
}
public int size() {
return list.size();
}
public boolean isEmpty() {
if(list.size() == 0)
return true;
return false;
}
public void swap(int i,int k) {
PQEntry temp = list.get(i);
list.set(i, list.get(k));
list.set(k, temp);
}
public void heapUp(int i) {
while (i>0){
int p = parent(i);
if(list.get(i).getValue() >= list.get(p).getValue()) break;
swap(i,p);
i = p;
}
}
public boolean hasleft(int i) {
return (2*i + 1 < list.size());
}
public boolean hasright(int i) {
return (2*i + 2 < list.size());
}
public void heapDown(int i) {
int leftindex,rightindex;
while (hasleft(i)) {
leftindex = 2*i + 1;
int smallchildindex = leftindex;
if (hasright(i)) {
rightindex = 2*i+2;
if (list.get(leftindex).getValue() > list.get(rightindex).getValue())
smallchildindex = rightindex;;
}
if (list.get(i).getValue() <= list.get(smallchildindex).getValue()) break;
swap(i, smallchildindex);
i = 2*i + 1;
}
}
public PQEntry insert(Integer key, String value) {
PQEntry newestl = null;
newestl.setValue(key);
heap.add(heap.size(), value);
heapUp(heap.size()-1);
return newestl;
}
private void add(int size, String value) {
// TODO Auto-generated method stub
}
public PQEntry removeMin() {
if (heap.isEmpty()) return null;
swap (0, heap.size() - 1);
PQEntry answer = heap.remove(heap.size() - 1);
heapDown(0);
return answer;
}
private PQEntry remove(int i) {
// TODO Auto-generated method stub
return null;
}
public PQEntry min() {
if (heap.isEmpty()) return null;
return list.get(0);
}
}
AbstractPQueue.java
import java.util.ArrayList;
public abstract class AbstractPQueue implements PQueue{
//public abstract void removeMin(ArrayList
private EntryComparator comp;
protected AbstractPQueue() {
this(new EntryComparator());
}
protected AbstractPQueue(EntryComparator c) {
comp=c;
}
protected EntryComparator compare(PQEntry a, PQEntry b) {
return comp;
}
public void removeMin(ArrayList
// TODO Auto-generated method stub
}
}
PQEntry.java
class PQEntry {
private int key;
private String value;
public PQEntry() {
this(-1,null);
}
public PQEntry(int k, String v) {
this.key=k;
}
public String getValue() {
return this.value;
}
public int getkey() {
// TODO Auto-generated method stub
return 0;
}
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help