Solved

Help implementing some methods getting errors

Posted on 2009-04-10
31
415 Views
Last Modified: 2012-05-06
Hello,

I am attempting to create a program that accomplishes the following:

*I am to develop a heap, that is tree-based(not array)

*The heap should be ascending

*Include the method toss()
-This method will randomly toss a node into the heap and will not maintain the proper heap conditions

*Include restoreHeap() method
- In the application, after calling the toss() method a few times. Utilize restoreHeap() to reposition the tossed nodes into their proper location according to the conditions of a heap


Here are my current errors:


Error 1: public class treeHeap<E extends Comparable<E>> extends AbstractCollection<E> {

Message: Must implement the inheirted abstract



Error 2: public boolean toss(E value) {

Message: Must return result type boolen



Error 3:

      public void restoreHeap() {
            if (node != root && node.compareTo(node.parent) > 0) {
                  swapValues(node, node.parent);
                  bubbleUp(node.parent);
            }
      }

Message:  Node cannot be resolved




I need to create an app that utilizes TOSS and RESTOREHEAP methods.

Furthermore, my current restore heap I believe will need some sort of in order traversal statements, so that it visits each node in ascending order then puts them in their correct location in the heap.


Any other inline comments are very appreciated to accomplish this task. I am very understanding of the logic, however, my java syntax is not so great.

Thank you
import java.util.AbstractCollection;

import java.util.LinkedList;

import java.util.Queue;
 

/**

 * 

 * 

 *

 */

public class treeHeap<E extends Comparable<E>> extends AbstractCollection<E> {
 

	// A single container for element in heap tree.
 

	private class Node {

		E value;

		Node parent;

		Node left;

		Node right;
 

		Node(E value) {

			this.value = value;

			parent = null;

			left = null;

			right = null;

		}
 

		E getValue() {

			return value;

		}
 

		int compareTo(Node node) {

			return (value.compareTo(node.value));

		}

	}
 

	Node root;
 

	/**

	 * Creates an empty heap tree.

	 */
 

	public treeHeap() {

		root = null;

	}
 

	/**

	 * Creates a heap tree with specified element.

	 */
 

	public treeHeap(E value) {

		root = new Node(value);

	}
 

	/**

	 * 

	 * @

	 * 

	 */
 

	void swapValues(Node p, Node q) {

		E temp = p.value;

		p.value = q.value;

		q.value = temp;

	}
 

	// Finds and returns a parent for new Node.
 

	private Node getFreeParent() {

		Queue<Node> queue = new LinkedList<Node>();

		queue.add(root);

		Node temp;

		while (queue.peek() != null) {

			if (queue.peek().left != null && queue.peek().right != null) {

				temp = queue.remove();

				queue.add(temp.left);

				queue.add(temp.right);

			} else

				return queue.peek();

		}

		return null;

	}
 

	/**

	 * 

	 * 

	 *

	 */
 

	public boolean toss(E value) {

		if (root == null) {

			root = new Node(value);

		} else {

			Node newNode = new Node(value);

			Node freeParent = getFreeParent();

			newNode.parent = freeParent;

			if (freeParent.left == null) {

				freeParent.left = newNode;

			} else {

				freeParent.right = newNode;

			}// end second else

			return true;

		}// end first else
 

	}// end toss()
 

	/**

	 * 

	 * THIS METHOD NEEDS SOME TYPE OF INORDER TRAVERSAL STATEMENTS SO THAT IT

	 * VISITS EACH NODE APPLYING THESE RULES SO THAT THE TOSSED NODES WILL FIND

	 * THEIR PROPER LOCATION IN ASCENDING ORDER

	 * 

	 */

	public void restoreHeap() {

		if (node != root && node.compareTo(node.parent) > 0) {

			swapValues(node, node.parent);

			bubbleUp(node.parent);

		}

	}
 

}// end treeHeap Class
 

/**

 * 

 * 

 *

 */
 

class treeHeapApp {

	public static void main(String[] args) {

		treeHeap theTreeHeap = new treeHeap(31);
 

		theTreeHeap.toss(15);

		theTreeHeap.toss(87);

		theTreeHeap.toss(51);

		theTreeHeap.toss(62);

		theTreeHeap.toss(8);

		theTreeHeap.toss(41);

		theTreeHeap.toss(12);

		theTreeHeap.toss(66);

		theTreeHeap.toss(24);

		theTreeHeap.toss(99);
 

		theTreeHeap.restoreHeap();
 

	}

}

Open in new window

0
Comment
Question by:ViLeNT
  • 15
  • 13
  • 2
31 Comments
 
LVL 17

Expert Comment

by:Thomas4019
ID: 24118766
The problem with your method "boolean toss()" is that it only has one return statement which means it might not return anything. In java, if a method has a return type, it must return a valid object of that type. Basically, for each case of the method, it must return something.
0
 
LVL 40

Expert Comment

by:RQuadling
ID: 24119839
The only thing toss() could return which is meaningful, if it has to return a boolean, is a false if there was no root and one was created by the toss. You can't toss 1 item.

If that is the case then ...
        public boolean toss(E value) {

                if (root == null) {

                        root = new Node(value);

                        // False indicates no toss took place.

                        return false;

                } else {

                        Node newNode = new Node(value);

                        Node freeParent = getFreeParent();

                        newNode.parent = freeParent;

                        if (freeParent.left == null) {

                                freeParent.left = newNode;

                        } else {

                                freeParent.right = newNode;

                        }// end second else

                        return true;

                }// end first else

 

        }// end toss()

 

Open in new window

0
 
LVL 17

Expert Comment

by:Thomas4019
ID: 24119886
That should fix your error 2. I will lookover your other erros
0
 

Author Comment

by:ViLeNT
ID: 24119891
How do I go about modifying restoreHeap and Toss methods to meet my specifications? Currently, toss may be called in an application to toss a set of numbers into the heap. However, how this is setup, each time a number is tossed, its proper location in the heap is automatically found because restoreHeap() is called.


How do I modify toss to just toss integers into the next available parent?
Then modify restoreHeap to go through in ascending order to cleanup the heap to heap specifications?
import java.util.*;
 

/**

 * The purpose of this program is to formulate a tree-based heap instead of the

 * typical array based heap. The toss method may be utilized to add nodes

 * containing integers to the tree-based heap. Nodes may be continuously tossed

 * onto the heap one by one. Once it is time to restore the heap to proper heap

 * specifications, the method heapRestore is then called.

 * 

 * @author Vince Guadalue

 */
 

////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
 

public class treeHeap<Element extends Comparable<Element>> {
 

	Node root;
 

	/**

	 * This method will create an empty tree Heap for nodes to be inserted on

	 */
 

	public treeHeap() {

		root = null;

	}
 

	/**

	 * The purpose of this method is to create a tree heap with a specific node,

	 * setting the node as the root value

	 */
 

	public treeHeap(Element data) {

		root = new Node(data);

	}
 

////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
 

	/**

	 * This class serves as container for an element in the tree heap

	 */
 

	private class Node {

		Element data;

		Node parent;

		Node leftChild;

		Node rightChild;
 

		/**

		 * This is the constructor for the node class it will set the parent,

		 * left and right child to null

		 */

		Node(Element value) {

			this.data = value;

			parent = null;

			leftChild = null;

			rightChild = null;

		}// end Constructor
 

		/**

		 * This method will compare node objects to help determine if they are in the

		 * correct order. This is utilized in the heapRestore method

		 */

		int compareThem(Node node) {

			return (data.compareTo(node.data));

		}// end compareTo()

	}// end class Node
 

////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
 

	/**

	 * This method works hand-and-hand with the toss method. Before an item can

	 * be tossed onto the tree heap an open parent for the tossed node must be

	 * located to attach itself too.

	 */
 

	private Node openParent() {

		Queue<Node> queue = new LinkedList<Node>();

		queue.add(root);

		Node temp;

		while (queue.peek() != null) {

			if (queue.peek().leftChild != null

					&& queue.peek().rightChild != null) {

				temp = queue.remove();

				queue.add(temp.leftChild);

				queue.add(temp.rightChild);

			} else

				return queue.peek();

		}

		return null;

	}
 

	/**

	 * Toss is going to add a new node to the tree heap utilizing the openParent

	 * method. Once an open parent is located the new node is inserted.

	 */
 

	public boolean toss(Element value) {

		if (root == null) {

			root = new Node(value);

		} else {

			Node newNode = new Node(value);

			Node freeParent = openParent();

			newNode.parent = freeParent;

			if (freeParent.leftChild == null) {

				freeParent.leftChild = newNode;

			} else {

				freeParent.rightChild = newNode;

			}

			restoreHeap(newNode);

		}

		return true;

	}
 

	/**

	 * This method is utilized to swap values within the tree heap when called

	 * by the restoreHeap method. It helps maintain the correct structure of a

	 * heap after items are randomly tossed in.

	 */

	void swapNodes(Node one, Node two) {

		Element temp = one.data;

		one.data = two.data;

		two.data = temp;

	}// end swapNodes()
 

	/**

	 * When a new node is added to the heap it must then be directed to its

	 * correct location following the properties of heaps. restoreHeap is

	 * utilized in the toss method after a node is randomly attached to the

	 * first open parent. restoreHeap will find the tossed nodes final and

	 * correct location on the tree heap.

	 */
 

	private void restoreHeap(Node node) {

		if (node != root && node.compareThem(node.parent) > 0) {

			swapNodes(node, node.parent);

			restoreHeap(node.parent);

		}// end if clause

	}// end restoreHeap()

}
 

////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////

Open in new window

0
 
LVL 40

Expert Comment

by:RQuadling
ID: 24120058
What would happen if toss() didn't call restoreHeap()?
0
 

Author Comment

by:ViLeNT
ID: 24120081
Well I would assume, it would then not restore the heap at that point in time to proper heap specification, which is of course what I need. Is this correct? If so, how would I slightly modify toss?

Once toss is modified its just a matter of then modifying restoreHeap(). Once this is called in the application, it should then traverse through the tree "inorder" or ascending order and restore the tree to heap specifications.

However, I am stuck as to how to do this.
0
 
LVL 40

Expert Comment

by:RQuadling
ID: 24120148
I'm confused.

You want to through data in willy-nilly and NOT have it sorted.

So, remove restoreHeap from toss.

Some time later, you want the heap sorted, call restoreHeap surely?
0
 

Author Comment

by:ViLeNT
ID: 24120183
YES SIR! that is correct. It may not make sense now, but apparently, it is more efficient to toss objects onto the heap and then restore the heap in the end. Instead of one by one toss, restore, toss, restore, toss, restore. See what I am saying?

How would I go about modifying restoreHeap so that I may call it after tossing items onto the heap to traverse through the entire heap and restore it to heap specifications.
0
 
LVL 40

Expert Comment

by:RQuadling
ID: 24120261
You have to manually call restoreHeap once you've tossed in all the items.

The heap doesn't know when how many items you've got to toss in.
0
 

Author Comment

by:ViLeNT
ID: 24120287
Yes thats just fine, in fact that is my objective. To manually toss items, then manually call restore heap in the application of my program. In this case, how would such an application look that utilizes these methods?

Would something like below work? How can I fix this to pass the correct parameters to toss, to toss a node into the heap. Will my current manually restoreHeap call work in ascending order? Is it going to go through the entire heap and reorganize it to proper heap specifications?
class treeHeapApp {

	public static void main(String[] args) {

		

toss(#);

toss(#);

toss(#);

toss(#);

restoreHeap();
 

	} // end main()

} // end class treeHeapApp

Open in new window

0
 
LVL 40

Expert Comment

by:RQuadling
ID: 24120323
I don't know the algorithm for sorting the heap like you want.
0
 

Author Comment

by:ViLeNT
ID: 24120337
Well perhaps this will help?

"An inorder traversal of a binary search tree will cause all the nodes to be visited in ascending order"

"The simplest way to carry out traversal is the use of recursion"

1. Call itself to traverse the node's left subtree
2. Visit the node
3. Call itself to traverse the node's right subtree

Does this help?
private void inOrder(Node localRoot)

{

if(localRoot !=null)

{

inorder(LocalRoot.leftChild);

inOrder(Localroot.rightChild);

}

}

Open in new window

0
 
LVL 40

Expert Comment

by:RQuadling
ID: 24120379
You could speed up adding things by remembering the last node you added and always adding to the left hand side of the tree.

So a new private property of the heap would be something like ...

Node lastNodeAdded;

And in see snippet for a new toss (UNTESTED - May have typos - follow logic and comments).

So, initially, all nodes would be added into the left path.
       public boolean toss(E value) {

                // Track a result boolean

       		boolean bResult;
 

                // We are always going to need a new node,

                // so only ask once.

                Node newNode = new Node(value);
 

		// If the root is empty, then the new node

		// is the root.

                if (root == null) {

                        root = newNode;

	                // False indicates no toss took place.

                        bResult = false;

                } else {

                	// The new nodes parent is the last

                	// node we added.

                        newNode.parent = lastNewNode;

                        

                        // Determine if the new node is a left

                        // or right child of its parent.

                        if (lastNewNode.left == null) {

                                lastNewNode.left = newNode;

                        } else {

                                lastNewNode.right = newNode;

                        }// end second else

                        

                        bResult = true;

                }// end first else
 

                // Tell the heap where to send new nodes in future.

                lastNewNode = newNode;
 

		// Return the result.

                return bResult;

        }// end toss()

Open in new window

0
 
LVL 40

Expert Comment

by:RQuadling
ID: 24120383
So now to the sorting. This is where I get confused.

Unless you know a mid point in the values, you will end up with a very heavily one-sided tree?


0
 

Author Comment

by:ViLeNT
ID: 24120392
If the tree starts off empty, wouldn't such an implementation result in a sequentially linked list?
0
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 

Author Comment

by:ViLeNT
ID: 24120410
Originally this project started off Array Based but needed to be converted to "Tree Based" which is why I am using a Tree and Nodes.

I dont think it matters that I end up with a heavily sided tree, it just needs to be "tree-based" implementation. Not necessarily look like a tree visually.

So if we do in fact use your implementation to insert items only to the left. We can then design a heapRestore method to traverse through this list comparing each node to another and swapping where neccessary after we are done tossing nodes to it.

Does this sound logical?
0
 
LVL 40

Expert Comment

by:RQuadling
ID: 24120425
Yes.
0
 

Author Comment

by:ViLeNT
ID: 24120430
Well, any ideas how we would go about implementing a restore method now? :)
0
 
LVL 40

Expert Comment

by:RQuadling
ID: 24120434
I think.
0
 
LVL 40

Expert Comment

by:RQuadling
ID: 24120444
http://en.wikipedia.org/wiki/Heapsort goes into some detail.
0
 

Author Comment

by:ViLeNT
ID: 24120455
It would basically have to then sequentially go through the list of nodes we tossed and be sure that each node in the heap satisfies the heap condition. Which states that ever node's key is larger than (or equal to) the keys of its children.
0
 

Author Comment

by:ViLeNT
ID: 24120472
Hmm..here is an Array Based way of using Heap Sort

Could we modify this to be tree-based?

http://www.ehow.com/how_2094984_use-heapsort-java.html?ref=fuel&utm_source=yahoo&utm_medium=ssp&utm_campaign=yssp_art
0
 
LVL 40

Expert Comment

by:RQuadling
ID: 24120498
0
 

Author Comment

by:ViLeNT
ID: 24120507
Yes but this is array based are we able to transform this to Tree-based?
0
 

Author Comment

by:ViLeNT
ID: 24120526
For example
Just have to go through and transition from array to tree.
This is Array:
 

This is Tree-Based

	void swapValues(Node p, Node q) {

		E temp = p.value;

		p.value = q.value;

		q.value = temp;

	}
 
 

This is Array-Based

    public static final void swapReferences( Object [ ] a, int index1, int index2 )

    {

        Object tmp = a[ index1 ];

        a[ index1 ] = a[ index2 ];

        a[ index2 ] = tmp;

    }

Open in new window

0
 
LVL 40

Expert Comment

by:RQuadling
ID: 24120538
0
 

Author Comment

by:ViLeNT
ID: 24120551
All array based unfortunately.
0
 

Author Comment

by:ViLeNT
ID: 24120563
Do you have the proper java background to be able to help me transition this array based implementation to tree based?
0
 
LVL 40

Accepted Solution

by:
RQuadling earned 500 total points
ID: 24120567
Sorry. No. Mine is PHP.
0
 

Author Comment

by:ViLeNT
ID: 24120596
Is this a way we could possible get an expert in here who specializes in java? I appreciate your time.
0

Featured Post

Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

Join & Write a Comment

The purpose of this article is to demonstrate how we can use conditional statements using Python.
Introduction This article is the second of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers the basic installation and configuration of the test automation tools used by…
The viewer will learn how to implement Singleton Design Pattern in Java.
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…

706 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

17 Experts available now in Live!

Get 1:1 Help Now