Required files: MinHeap.java and Test.java Implement of the MinHeap class The AD
ID: 3918986 • Letter: R
Question
Required files: MinHeap.java and Test.java
Implement of the MinHeap class
The ADT of the MinHeap class is given below:
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;
}
Explanation / Answer
MinHeap.java
package com.src;
import java.util.ArrayList;
public class MinHeap extends AbstractPQueue {
private ArrayList<PQEntry> 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);
}
}
Test this class with your driver class. Let me know if you don't have any.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.