Help with Tree-based implementation

[ViLeNT]

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

Currently below is what I have, unfortunately, I am only able to make toss and restoreHeap array based. Could someone please provide inline comments on the proper way to change my current methods to tree-based?

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 and I look forward to working with you!!

/**
 * 
 * 
 *
 */
class theNode
{
        private int data;
        
        public theNode (int theData)
        {
                data = theData;
        }
 
        public int getit()
        {
                return data;
        }
 
        public void setit(int theData)
        {
                data = theData;
        }
        
}//end theNode class
 
/**
 * 
 * 
 *
 */
public class treeHeap
{
        private theNode[] heapArray;
        private int treeSize;
        private int Elems;
        private int index;
        
 
        /**
         * 
         * 
         *
         */
        public treeHeap(int theSize)
        {
                treeSize = theSize;
                Elems = 0;
                heapArray = new theNode[treeSize];
        }
 
        
        /**
         * 
         * 
         *
         */
        public void toss(int tossIt)
        {
                int data = Elems;
                
                theNode newNode = new theNode(tossIt);
                
                heapArray[Elems] = newNode;
                
                while(data >= 1)
                {
                        heapArray[tossIt++] = data % 2;
                        data = data / 2;
                }
                
                Elems++;                        
        }//end toss()
        
 
        /**
         * 
         * 
         *
         */
        public void restoreHeap()
        {
                int parent = (index - 1) / 2;
                theNode bottom = heapArray[index];
                while(index > 0 && heapArray[parent].getit() < bottom.getit())
                {
                        heapArray[index] = heapArray[parent];
                        index = parent;
                        parent = (parent - 1) / 2;
                }
                heapArray[index] = bottom;
                
                System.out.println();
        }
        
        
}//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();
                
                
        }
}

[ViLeNT]

What's the problem? Does no one have any input what so ever?

[BestJewSinceJC]

I took a look at your problem yesterday, but I can't say I remember enough about the data structure to be very helpful as far as the logic. But if it is the syntax you are struggling with, ask a specific question about what you are trying to accomplish (as far as the logic) and I'd be glad to help you with it.

[ViLeNT]

[B]Error 1:[/B] public class treeHeap<E extends Comparable<E>> extends AbstractCollection<E> {

[B]Message: [/B]Must implement the inheirted abstract

[B]Error 2: [/B]public boolean toss(E value) {

[B]Message:[/B] Must return result type boolen

[B]Error 3:[/B]

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

[B]Message:[/B]  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.

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

	}
}

[BestJewSinceJC]

Error 1: Your class extends an abstract class, so you need to implement the abstract methods in that class. So basically, look at the AbstractCollection class, and make sure your class has all of the methods that AbstractCollection lists as 'abstract'.

Error 2: Your method has to return a boolean value. In Java, boolean values are declared as boolean variableName = true; or boolean variableName = false. You have to return a boolean.

Error 3: I have no idea. Usually this message means you are referring to a variable that doesn't exist within that method or class.

As for your other problems, you aren't saying anything that can't be grabbed from a project description. You said you 'knew the logic', so start programming. If you don't know how to implement a specific piece of logic, ask for help on that. "In order traversal" is not specific. (Yes, I know what inorder traversal is, but it has multiple steps - if you need help with doing one, you should be providing some code and asking about it, etc)