Can somebody please help me complete this to implement a MaxHeap. I have done as
ID: 3918196 • Letter: C
Question
Can somebody please help me complete this to implement a MaxHeap. I have done as much as I could figure out.
import java.util.NoSuchElementException;
import java.util.Vector;
/*
* The shell of the class, to be completed as part
* of CSC115 Assignment 5: Emergency Room.
*/
/*
* Complete this class as per the Heap.html specification document.
* Fill in any of the parts that have the comment:
* /******** COMPLETE *******/
/*
* Do not change method headers or code that has been supplied.
* Delete all messages to you, including this one, before submitting.
*/
public class Heap1<E extends Comparable<E>> {
private Vector<E> heapArray;;
//default constructor
public Heap1() {
heapArray= new Vector <E>();
}
//public Heap1(comparable)
/**
@Returns True if heap is empty and false if it is not.
*/
public boolean isEmpty(){
return heapArray.size()==0;
}
/**
@Returns number of items in heap
*/
public int size(){
return heapArray.size();
}
/**
Retrieves, without removing the item in the root.
@returns top item in tree
@throws NoSuchElementExceptionif heap empty
*/
public E getRootItem() throws NoSuchElementException{
if(isEmpty()){
return null;
}
return heapArray.firstElement();
}
/**
Removes the item in the root.
@returns item at root of heap
@throws NoSuchElementException if heap empty
*/
public E removeRootItem() throws NoSuchElementException{
if(isEmpty()){
throw new NoSuchElementException("Heap Empty");
}
int index=0;
return heapArray.remove(index);
}
//To use to reheap up when item inserted at end of heap (complete tree)
private void bubbleUp(E x){
int place = heapArray.size()-1;
int parent=(place-1)/2;
if ((parent>=0) && (parent.compareTo(heapArray.get(getLeftChild))<0)){
swap(place,parent);
}else ((parent>=0 && (parent.compareTo(heapArray.get(getRightChild))<0))){
swap(place,parent);
}
}
//swaps two objects at index i and j
private void swap(int i, int j){
int max=heapArray.size();
if(i>=0 && i<max && j>=0 && j<max){
E temp=heapArray.get(i);
//put J item in I
heapArray.set(i,heapArray.get(j));
heapArray.set(j,temp);
}
}
//to use to reheap down when item deleted from top of heap
private void bubbleDown(int x){
}
public static void main(String [] args){
}
}
Explanation / Answer
Please find the modified code below.
import java.util.NoSuchElementException;
import java.util.Vector;
public class Heap1<E extends Comparable<E>> {
private Vector<E> heapArray;;
//default constructor
public Heap1() {
heapArray= new Vector <E>();
}
//public Heap1(comparable)
/**
@Returns True if heap is empty and false if it is not.
*/
public boolean isEmpty(){
return heapArray.size()==0;
}
/**
@Returns number of items in heap
*/
public int size(){
return heapArray.size();
}
/**
Retrieves, without removing the item in the root.
@returns top item in tree
@throws NoSuchElementExceptionif heap empty
*/
public E getRootItem() throws NoSuchElementException{
if(isEmpty()){
return null;
}
return heapArray.firstElement();
}
/**
Removes the item in the root.
@returns item at root of heap
@throws NoSuchElementException if heap empty
*/
public E removeRootItem() throws NoSuchElementException{
if(isEmpty()){
throw new NoSuchElementException("Heap Empty");
}
int index=0;
return heapArray.remove(index);
}
private int getLeftChild(int i) {
return 2*i + 1;
}
private int getRightChild(int i) {
return 2*i + 2;
}
//To use to reheap up when item inserted at end of heap (complete tree)
private void bubbleUp(E x){
int place = heapArray.size()-1;
int parent=(place-1)/2;
if ((parent>=0) && (heapArray.get(parent).compareTo(heapArray.get(getLeftChild(place)))<0)){
swap(place,parent);
}else if ((parent>=0) && (heapArray.get(parent).compareTo(heapArray.get(getRightChild(place)))<0)){
swap(place,parent);
}
}
//swaps two objects at index i and j
private void swap(int i, int j){
int max=heapArray.size();
if(i>=0 && i<max && j>=0 && j<max){
E temp=heapArray.get(i);
//put J item in I
heapArray.set(i,heapArray.get(j));
heapArray.set(j,temp);
}
}
private int kthChild(int i, int k) {
return 2 * i + k;
}
private int maxChild(int x) {
int bestChild = kthChild(x, 1);
int k = 2;
int pos = kthChild(x, k);
while ((k <= 2) && (pos < heapArray.size()))
{
if (heapArray.get(pos).compareTo(heapArray.get(bestChild)) > 0)
bestChild = pos;
pos = kthChild(x, k++);
}
return bestChild;
}
//to use to reheap down when item deleted from top of heap
private void bubbleDown(int x){
int child;
E tmp = heapArray.get(x);
while (kthChild(x, 1) < heapArray.size())
{
child = maxChild(x);
if (heapArray.get(child).compareTo(tmp) > 0)
heapArray.set(x, heapArray.get(child));
else
break;
x = child;
}
heapArray.set(x, tmp);
}
public static void main(String [] args){
}
}