Solved

JAVA EXPERT: Help create method please

Posted on 2009-04-10
6
289 Views
Last Modified: 2012-05-06
I am attempting to create two methods both tree-based implementations.

#1
Toss: Toss places a new node in the heap without attempting to maintain the heap condition

#2
restoreHeap: Restores the heap condition throughout the entire heap.

The application will manually toss nodes into the heap, then restore the heap
Example:

toss(#);
toss(#);
toss(#);
toss(#);
restoreHeap();

Please help me formulate a tree-based method restoreHeap() that will traverse through the tree-based heap restoring the heap condition through the entire heap.

Below is my code to toss a random node onto the heap.

Please java experts are needed, Ive been at this for hours. Only implementations I can find are array based unfortunately.
public boolean toss(Element value) {
		//if the root is empty
		if (root == null) { 
			
			//create a new node and call it root
			root = new Node(value);
			
		} else { //otherwise
			
			//create a node called new Node
			Node newNode = new Node(value);
			
			//create a node, this being the next open parent
			Node aParent = openParent(); 
			
			//the new node parent is the open parent
			newNode.parent = aParent;
			
			//if the parents left child is open
			if (aParent.leftChild == null) { 
				
			//designate the left child and insert the new node there
				aParent.leftChild = newNode; 
				
			} else { //otherwise
				
			//insert the new node as the right child
				aParent.rightChild = newNode; 
				
			}//end second else
		}//end first else
		
		return true;
	}//end toss()

Open in new window

0
Comment
Question by:ViLeNT
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 5
6 Comments
 
LVL 19

Accepted Solution

by:
Jim Cakalic earned 500 total points
ID: 24122111
What do you mean by "heap condition"? Is the end result supposed to be a balanced binary tree?
0
 

Author Comment

by:ViLeNT
ID: 24122425
Jim! The expert I have been waiting for!

By "heap condition" I mean once "restoreHeap" is called manually in the app after manually tossing a few nodes onto the heap its going to satisfy these conditions

The Heap Condition: States that every node's key is larger than(or equal to) the keys of its children.

Therefore, this restore heap algorithm needs to traverse through the tree in ascending order, and restore every node that I tossed in to their proper place.

Please ask if I am unclear and I have been unable to receive much help on this.
0
 

Author Comment

by:ViLeNT
ID: 24122450
Below is my current code.

As you can see currently In "toss" "restoreHeap" is called to ensure the node meets the heap condition.

However, this is not the correct application I wish to use.

I must toss "n" number of nodes. Then after I am done tossing. Restore the heap.

Therefore modifications are needed in the restoreHeap method to traverse through the tossed items and put them in their proper place.
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.
 * 
 * 
 */
 
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
 
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() 
    {
		//This will create a Queue object that holds the data of type Node
        Queue<Node> queue = new LinkedList<Node>(); 
        
        //This will add the object to the Queue with the name 'root'
        queue.add(root);
        
        //This declares a variable named 'temp' 
        Node temp;  
        
        //Loop while the next item in the queue is not null
        while (queue.peek() != null) {
            /*
             * Verify that the Node's leftChild and rightChild from the 
             * instance of Node that is next in the Queue are not null
             */
            if (queue.peek().leftChild != null
                    && queue.peek().rightChild != null) {
            	
            
            	//Remove the object from the front of the queue
            	//and reference temp to it
                temp = queue.remove(); 
                
                //Adds temps field 'leftChild' to the Queue
                queue.add(temp.leftChild);  
                
                //Adds temps field 'rightChild' to the Queue
                queue.add(temp.rightChild);
            } else
            	
                //The children of the Node are null, return the Node itself
                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 the root is empty
		if (root == null) { 
			
			//create a new node and call it root
			root = new Node(value);
			
		} else { //otherwise
			
			//create a node called new Node
			Node newNode = new Node(value);
			
			//create a node, this being the next open parent
			Node aParent = openParent(); 
			
			//the new node parent is the open parent
			newNode.parent = aParent;
			
			//if the parents left child is open
			if (aParent.leftChild == null) { 
				
			//designate the left child and insert the new node there
				aParent.leftChild = newNode; 
				
			} else { //otherwise
				
			//insert the new node as the right child
				aParent.rightChild = newNode; 
				
			}//end second else
			restoreHeap(newNode);
		}//end first else
		
		return true;
	}//end toss()
 
	/**
	 * 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 the node being compared is is not 
		//the root and the node being compared is greater then its parent
		if (node != root && node.compareThem(node.parent) > 0) {
			
			//swap the node with its parent													
			swapNodes(node, node.parent); 
			
			//and restore the heap to heap specifications
			restoreHeap(node.parent); 
		}// end if clause
	}// end restoreHeap()
}
 
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

Open in new window

0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

Author Comment

by:ViLeNT
ID: 24123442
Jim are you there? Really would like yours or someone else expertise here :)
0
 

Author Comment

by:ViLeNT
ID: 24130973
Is no one up to this challenge?
0
 

Author Closing Comment

by:ViLeNT
ID: 31569140
Delete this please
0

Featured Post

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Bot application - advice 3 80
Link failure 16 89
Java List 4 76
Read CLOB data from Oracle using JAVA 3 40
This article will show, step by step, how to integrate R code into a R Sweave document
When there is a disconnect between the intentions of their creator and the recipient, when algorithms go awry, they can have disastrous consequences.
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …

732 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