Results 1 to 6 of 6
  1. #1
    MoozicFarm is offline Member
    Join Date
    Mar 2012
    Posts
    8
    Rep Power
    0

    Default Help with Max Heap remove method

    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());

    }

    }

  2. #2
    DarrylBurke's Avatar
    DarrylBurke is offline Forum Police
    Join Date
    Sep 2008
    Location
    Madgaon, Goa, India
    Posts
    11,423
    Rep Power
    20

    Default Re: Help with Max Heap remove method

    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
    If you're forever cleaning cobwebs, it's time to get rid of the spiders.

  3. #3
    MoozicFarm is offline Member
    Join Date
    Mar 2012
    Posts
    8
    Rep Power
    0

    Default Re: Help with Max Heap remove method

    Quote Originally Posted by DarrylBurke View Post
    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:
    Java Code:
    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:

    Java Code:
    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!

  4. #4
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,655
    Blog Entries
    7
    Rep Power
    21

    Default Re: Help with Max Heap remove method

    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
    cenosillicaphobia: the fear for an empty beer glass

  5. #5
    MoozicFarm is offline Member
    Join Date
    Mar 2012
    Posts
    8
    Rep Power
    0

    Default Re: Help with Max Heap remove method

    Quote Originally Posted by JosAH View Post
    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?

  6. #6
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,655
    Blog Entries
    7
    Rep Power
    21

    Default Re: Help with Max Heap remove method

    Quote Originally Posted by MoozicFarm View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. need help with the remove method on arrayList
    By ShinTec in forum New To Java
    Replies: 5
    Last Post: 02-16-2010, 09:38 AM
  2. no heap space... need more heap
    By anupam.kumar in forum Advanced Java
    Replies: 3
    Last Post: 02-08-2010, 04:42 PM
  3. Replies: 0
    Last Post: 09-21-2009, 11:33 AM
  4. how does the remove method work for sets and hashsets
    By haridharna in forum Advanced Java
    Replies: 4
    Last Post: 08-06-2007, 12:48 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •