Help with Max Heap remove method

[MoozicFarm]

So I am not sure where I am going wrong, but my remove method is not displaying the correct output. any ideas where the fault is. below is my class for the maxHeap and following is the tester. I believe the correct output should be "9 6 8 5 1 2 3 4".


import java.util.*;
public class MaxHeap<T extends Comparable<? super T>> {

private ArrayList<T> theHeap;
private int size;

public MaxHeap()
{
theHeap = new ArrayList<T>();
size = 0;
}

public int compare(int parentIndex, int childIndex, ArrayList <T> theHeap)
{
int result = (theHeap.get(parentIndex)).compareTo(theHeap.get(c hildIndex));
return result;

}

public void add(T newElement)
{
theHeap.add(size, newElement);
int swapIndex = size;
while(swapIndex > 0 && compare(swapIndex, parent(swapIndex), theHeap) > 0)
{
swap(parent(swapIndex), swapIndex, theHeap);
swapIndex = parent(swapIndex);

}
size++;
}

public T remove()
{
T result = theHeap.get(0);
theHeap.set(0, theHeap.get(size-1));
System.out.print(theHeap.get(0));
size --;
int i = size-1;

int j = 0;

while(true)
{
if((leftChild(j) == i) && (compare(leftChild(j), j, theHeap) > 0))
{
swap(j, leftChild(j), theHeap);
j = leftChild(j); continue;
}

if((rightChild(j) <= i) && compare(leftChild(j), rightChild(j), theHeap) >= 0 && (compare(leftChild(j), j, theHeap) >0))
{
swap(j, leftChild(j), theHeap);
j = leftChild(j);
continue;

}

if((rightChild(j) <= i) && (compare(rightChild(j), leftChild(j), theHeap) >0) && (compare(rightChild(j), j, theHeap) > 0))
{
swap(j, rightChild(j), theHeap);
j = rightChild(j);
continue;
}
if((rightChild(j) >= i) || (compare(rightChild(j), j, theHeap) <=0))
{
swap(j, leftChild(j), theHeap);
j = rightChild(j);
break;
}


}
return result;


}

public void swap(int parentIndex, int childIndex, ArrayList<T> theHeap)
{
T temp = theHeap.get(parentIndex);
theHeap.set(parentIndex, theHeap.get(childIndex));
theHeap.set(childIndex, temp);

}

public int parent(int childIndex)
{
return (childIndex-1)/2;
}

public int leftChild(int parentIndex)
{

return 2*parentIndex + 1;
}

public int rightChild(int parentIndex)
{
return 2*parentIndex + 2;
}


public String toString()
{
StringBuilder S = new StringBuilder();
for(int i = 0; i<size; i++)
{
S.append(theHeap.get(i) + " ");
}

return S.toString();
}



}


Tester



public class MaxHeapTester {

public static void main(String [] args)
{
System.out.println("This will test a maxHeap");

MaxHeap<Integer> mh = new MaxHeap<Integer>();
mh.add(10);
mh.add(9);
mh.add(8);
mh.add(6);
mh.add(1);
mh.add(2);
mh.add(3);
mh.add(4);
mh.add(5);
System.out.println(" ");
System.out.println("This is before anything is removed");
System.out.println(mh.toString());

mh.remove();
System.out.println("This is after remove");
System.out.println(mh.toString());

}

}

[DarrylBurke]

A moderator added the code tags for you in your last thread. Don't you think it's time you look around the FAQs and learn how to do this for yourself?

db

[MoozicFarm]

A moderator added the code tags for you in your last thread. Don't you think it's time you look around the FAQs and learn how to do this for yourself?

db

Sorry, I'm new at this.

Updated:

import java.util.*;
public class MaxHeap<T extends Comparable<? super T>> {
	
	private ArrayList<T> theHeap;
	private int size;
	
	public MaxHeap()
	{
		theHeap = new ArrayList<T>();
		size = 0;
	}
	
	public int compare(int parentIndex, int childIndex, ArrayList <T> theHeap)
	{
		int result = (theHeap.get(parentIndex)).compareTo(theHeap.get(childIndex));
		return result;
		
	}
	
	public void add(T newElement)
	{
		theHeap.add(size, newElement);
		int swapIndex = size;
	while(swapIndex > 0 && compare(swapIndex, parent(swapIndex), theHeap) > 0)
	{
		swap(parent(swapIndex), swapIndex, theHeap);
		swapIndex = parent(swapIndex);
		
	}
	size++;
	}
	
	public T remove()
	{
		T result = theHeap.get(0);
		theHeap.set(0,  theHeap.get(size-1));
		System.out.print(theHeap.get(0));
		size --;
		int i = size-1;
		
		int j = 0;
		
		while(true)
		{
			if((leftChild(j) == i) && (compare(leftChild(j), j, theHeap) > 0))
			{
				swap(j, leftChild(j), theHeap);
				j = leftChild(j); continue;
			}
			
			if((rightChild(j) <= i) && compare(leftChild(j), rightChild(j), theHeap) >= 0 && (compare(leftChild(j), j, theHeap) >0))
			{
				swap(j, leftChild(j), theHeap);
				j = leftChild(j);
				continue;
				
			}
			
			if((rightChild(j) <= i) && (compare(rightChild(j), leftChild(j), theHeap) >0) && (compare(rightChild(j), j, theHeap) > 0))
			{
				swap(j, rightChild(j), theHeap);
				j = rightChild(j);
				continue;
			}
			if((rightChild(j) >= i) || (compare(rightChild(j), j, theHeap) <=0))
			{
				swap(j, leftChild(j), theHeap);
				j = rightChild(j);
						break;
			}
			
			
		}
		return result;

		
	}
	
	public void swap(int parentIndex, int childIndex, ArrayList<T> theHeap)
	{
		T temp = theHeap.get(parentIndex);
		theHeap.set(parentIndex, theHeap.get(childIndex));
		theHeap.set(childIndex,  temp);
		
	}
	
	public int parent(int childIndex)
	{
		return (childIndex-1)/2;
	}
	
	public int leftChild(int parentIndex)
	{
		
		return 2*parentIndex + 1;
	}
	
	public int rightChild(int parentIndex)
	{
		return 2*parentIndex + 2;
	}
	
	
	public String toString()
	{
		StringBuilder S = new StringBuilder();
		for(int i = 0; i<size; i++)
		{
			S.append(theHeap.get(i) + " ");
		}
		
		return S.toString();
	}
	


}

Here is the tester:

public class MaxHeapTester {
	
	public static void main(String [] args)
	{
		System.out.println("This will test a maxHeap");
		
		MaxHeap<Integer> mh = new MaxHeap<Integer>();
		mh.add(10);
		mh.add(9);
		mh.add(8);
		mh.add(6);
		mh.add(1);
		mh.add(2);
		mh.add(3);
		mh.add(4);
		mh.add(5);
		System.out.println(" ");
		System.out.println("This is before anything is removed");
		System.out.println(mh.toString());
		
		mh.remove();
		System.out.println("This is after remove");
		System.out.println(mh.toString());
		
	}

}

again, I apologize for the ignorance.

Thanks!

[JosAH]

I wrote a blog article for this forum once (see the button near the top of this page) on the heap sort algorithm. It has the method(s) you're looking for.

kind regards,

Jos

[MoozicFarm]

I wrote a blog article for this forum once (see the button near the top of this page) on the heap sort algorithm. It has the method(s) you're looking for.

kind regards,

Jos

I am not sure if there are different conventional terms for remove() or not. Which method should I be looking at specifically?

[JosAH]

I am not sure if there are different conventional terms for remove() or not. Which method should I be looking at specifically?

If you're talking about my blog article: look at the 'phase2' method where the top of the heap (the first element in the array) is removed (swapped with the last element in the array) and the heap is 'heapified' again, starting at node #0.

kind regards,

Jos