Solved

EXPERT: Convert this to tree-based

Posted on 2009-04-13
4
429 Views
Last Modified: 2012-05-06
I'm looking to convert the following method to tree-based, its currently array based. Please guide me through this.
public void trickleUp(int index) {
    int parent = (index - 1) / 2;
    Node bottom = heapArray[index];
 
    while (index > 0 && heapArray[parent].getKey() < bottom.getKey()) {
      heapArray[index] = heapArray[parent]; // move it down
      index = parent;
      parent = (parent - 1) / 2;
    }
    heapArray[index] = bottom;
  }

Open in new window

0
Comment
Question by:ViLeNT
  • 3
4 Comments
 

Author Comment

by:ViLeNT
ID: 24147149
Thanks for nothing
0
 

Accepted Solution

by:
timhoustontx earned 500 total points
ID: 24147445
That's kind of vague--implementing one method when there must be a whole range of methods that implement the heap.


public void trickleUp(Node node) 
{
    Node parent = node.getParent();
 
    while (parent != null && 
           parent.getKey() < node.getKey()) 
    {
         swapParentWithChild(parent,node);
         child = parent;
         parent = node.getParent();
    }
  }
 
  swapParentWithChild(Node parent,Node child)
  {
      // swapping the actual nodes is quite confusing.
      // better is to swap the data and key of the nodes
  }

Open in new window

0
 

Author Comment

by:ViLeNT
ID: 24153382
Well I guess my current implementation is wrote...

This program is suppose to simply toss nodes into the tree heap and not maintain any order what-so-ever

So say I toss 5 nodes into the tree randomly. This is done using the Toss() method, which calls the openParent() method so it can find an open parent to attach a new node.

Then restoreHeap() needs to come on and traverse through the entire tree heap, and call trickleUp() to move nodes to their correct position in the heap.

Can you browse through my code and tell me where im going wrong? :-/
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;
	public int size = 0;
 
	/**
	 * 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);
				size++;
		} else { // otherwise
 
			// create a node called new Node
			Node newNode = new Node(value);
				size++;
 
			// 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;
					size++;
 
			} else { // otherwise
 
				// insert the new node as the right child
				aParent.rightChild = newNode;
					size++;
 
			}// end second else
 
		}// 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 trickleUp(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);
 
		}// end if clause
	}// end trickleUp()
	
	/**
	 *This method will traverse through the tree heap and utilize
	 *the trickleUp method to restore nodes to their proper location
	 */
	private void heapRestore(Node node) {
		int j;
		
		for(j=size/2-1; j >=0; j --)
			trickleUp(node);
 
	}//end heapRestore()
	
}//end treeHeap class
 
// //////////////////////////////////////////////////////////////////////////////
// //////////////////////////////////////////////////////////////////////////////

Open in new window

0
 

Author Closing Comment

by:ViLeNT
ID: 31569660
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
Android studio getdrawable(int) is deprecated 4 123
Should localization be done inside spring controller 5 32
hibernate jars 4 45
Crystal Reports Licensing Questions 4 37
Introduction Java can be integrated with native programs using an interface called JNI(Java Native Interface). Native programs are programs which can directly run on the processor. JNI is simply a naming and calling convention so that the JVM (Java…
Introduction This article is the first of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article explains our test automation goals. Then rationale is given for the tools we use to a…
This tutorial explains how to use the VisualVM tool for the Java platform application. This video goes into detail on the Threads, Sampler, and Profiler tabs.
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…

821 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