I am writing code for a generic implementation of a Heap. I\'d appreciate if som
ID: 3916492 • Letter: I
Question
I am writing code for a generic implementation of a Heap. I'd appreciate if someone could help me with the debugging. I have written all the code but in some places haven't considered coding for a generic class, which is probably the source of most errors.
import java.util.NoSuchElementException;
import java.util.Vector;
/*
* Complete this class as per the Heap.html specification document.
/*
* Do not change method headers or code that has been supplied.
* Delete all messages to you, including this one, before submitting.
*/
public class Heap<E extends Comparable<E>> {
private Vector<E> heapArray;
//declaring constant for the haeap branching factor
private static final int N=2;
/**
Create an empty heap
*/
public Heap() {
heapArray= new Vector <E>();
}
/**
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();
}
/**
@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();
}
/**
Inserts an item into the heap.
@param item newly added item
*/
public void insert(E item){
heapArray.add(item);
reHeapUp(heapArray.size()-1);
}
/**
public E getTop(){
if(isEmpty()){
return null;
}
return heapArray.firstElement();
*/
public E removeTop(){
if(isEmpty()){
return null;
}
E top = heapArray.firstElement();
heapArray.setElementAt(heapArray.lastElement(),0);
heapArray.remove(heapArray.size()-1);
reHeapDown(0);
return top;
}
public void swap(int i, int j){
int max= heapArray.size();
if(i>=0&&i<max&&j>=0&&j<max){
E temp = heapArray.elementAt(i);
heapArray.setElementAt(i,heapArray.elementAt(j));
heapArray.setElementAt(j,temp);
}
}
/**
Removes the item in the root.
@returns item at root of heap
@throws NoSuchElementException if heap empty
*/
public E removeRootItem() throws NoSuchElementException{
}
private void printHeap(){
for(int i=o;i<heapArray.size();i++){
System.out.print(heapArray.elementAt(i).toString());
System.out.print(" ");
}
System.out.println(" ");
}
private int getFirstChild(int x){
return x*N+1;
}
private int getParent(int x){
return (x-1)/N;
}
private int getHighestChild(E x){
int firstChild = getFirstChild(x);
if(firsrChild>=heapArray.size()){
return -1;
}
int bestChild=firsrChild;
Element bestH=heapArray.elementAt(firsrChild);
for(int i=1;i<N;i++){
if(firsrChild+i>=heapArray.size()){
return bestChild;
}
heapArray cuurH= heapArray.elementAt(firsrChild+i);
if(currH.HigherPriorirty(bestH)){
bestChild=firsrChild+i;
bestH=currH;
}
}
return bestChild;
}
private void reHeapUp(E x) {
if(x==0){
return;//means we are at top
}
int prevIndex=getRootItem(x);
heapArray currElement = heapArray.elementAt(x);
heapArray prevElement = heapArray.elementAt(prevIndex);
if(currElement.HighestPriority(prevElement)){
//swap this with parent and reHeapify
swap(prevIndex,x);
reHeapUp(prevIndex);
}
}
private void reHeapDown(E x){
int highChild = getHighestChild(x);
if(highChild<0){//no children
return;
}
heapArray currElement = heapArray.elementAt(x);
heapArray childElement = heapArray.elementAt(highChild);
if(childElement.HigherPriorirty(currElement)){
swap(x,highChild);
reHeapDown(highChild);
}
}
public static void main( String[]args){
}
}
Explanation / Answer
Please find the modified code below.
CODE
===========
import java.util.NoSuchElementException;
import java.util.Vector;
/*
* Complete this class as per the Heap.html specification document.
/*
* Do not change method headers or code that has been supplied.
* Delete all messages to you, including this one, before submitting.
*/
public class Heap<E extends Comparable<E>> {
private Vector<E> heapArray;
//declaring constant for the haeap branching factor
private static final int N=2;
/**
Create an empty heap
*/
public Heap() {
heapArray= new Vector <E>();
}
/**
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();
}
/**
@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();
}
/**
Inserts an item into the heap.
@param item newly added item
*/
public void insert(E item){
heapArray.add(item);
reHeapUp(heapArray.size()-1);
}
/**
public E getTop(){
if(isEmpty()){
return null;
}
return heapArray.firstElement();
*/
public E removeTop(){
if(isEmpty()){
return null;
}
E top = heapArray.firstElement();
heapArray.setElementAt(heapArray.lastElement(),0);
heapArray.remove(heapArray.size()-1);
reHeapDown(0);
return top;
}
public void swap(int i, int j){
int max= heapArray.size();
if(i>=0&&i<max&&j>=0&&j<max){
E temp = heapArray.elementAt(i);
heapArray.setElementAt(heapArray.elementAt(j),i);
heapArray.setElementAt(temp,j);
}
}
/**
Removes the item in the root.
@returns item at root of heap
@throws NoSuchElementException if heap empty
*/
public E removeRootItem() throws NoSuchElementException{
// YOU NEED TO IMPLEMENT THIS METHOD
return null;
}
private void printHeap(){
for(int i=0;i<heapArray.size();i++){
System.out.print(heapArray.elementAt(i).toString());
System.out.print(" ");
}
System.out.println(" ");
}
private int getFirstChild(int x){
return x * N + 1;
}
private int getParent(int x){
return (x-1)/N;
}
private int getHighestChild(int x){
int firstChild = (int)getFirstChild(x);
if(firstChild >= heapArray.size()){
return -1;
}
int bestChild=firstChild;
E bestH = heapArray.elementAt(firstChild);
for(int i=1;i<N;i++){
if(firstChild + i>=heapArray.size()){
return bestChild;
}
E currH = heapArray.elementAt(firstChild + i);
if(currH.HigherPriorirty(bestH)){
bestChild=firstChild+i;
bestH=currH;
}
}
return bestChild;
}
private void reHeapUp(int x) {
if(x == 0){
return;//means we are at top
}
int prevIndex = (int)getRootItem();
E currElement = heapArray.elementAt(x);
E prevElement = heapArray.elementAt(prevIndex);
if(currElement.HighestPriority(prevElement)){
//swap this with parent and reHeapify
swap(prevIndex,x);
reHeapUp(prevIndex);
}
}
private void reHeapDown(int x){
int highChild = getHighestChild(x);
if(highChild<0){//no children
return;
}
E currElement = heapArray.elementAt(x);
E childElement = heapArray.elementAt(highChild);
if(childElement.HigherPriorirty(currElement)){
swap(x,highChild);
reHeapDown(highChild);
}
}
public static void main( String[]args){
}
}
NOTE: You would need to define the function removeRootItem(). For now, I am returning null. And I could not find anything called 'HigherPriorirty' which you have used in your code. So they are still throwing errors. Rest all errors are removed.