Need a driver program to make this class run. driver class should be named as Te
ID: 3919219 • Letter: N
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 {
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<Integer>arr1);
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<Integer> arr1) {
// 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;
}
}
Explanation / Answer
Please find the Test.java class below:-
1. Test.java
public class Test {
public static void main(String[] args) {
MinHeap minHeapObj = new MinHeap();
System.out.println("Min Heap empty? " + minHeapObj.isEmpty());
minHeapObj.insert(10, "Gopal");
minHeapObj.insert(20, "Malaker");
minHeapObj.insert(30, "Chegg");
minHeapObj.insert(40, "Bangalore");
System.out.println("Min Heap empty? " + minHeapObj.isEmpty());
System.out.println("Min Heap Size: " + minHeapObj.size());
System.out.println("Removing Minimum Element: " + minHeapObj.removeMin());
System.out.println("Removing Minimum Element: " + minHeapObj.removeMin());
System.out.println("Min Heap has Right element: " + minHeapObj.hasright(30));
System.out.println("Min Heap has Left element: " + minHeapObj.hasleft(30));
}
}
Please let me know in case of any clarifications required. Thanks!
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.