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

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.

Richard QuadlingSenior Software DeverloperCommented:

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

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()}////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

Richard QuadlingSenior Software DeverloperCommented:

What would happen if toss() didn't call restoreHeap()?

0

ViLeNTAuthor Commented:

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.

Richard QuadlingSenior Software DeverloperCommented:

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

ViLeNTAuthor Commented:

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.

Richard QuadlingSenior Software DeverloperCommented:

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

ViLeNTAuthor Commented:

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

Richard QuadlingSenior Software DeverloperCommented:

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

Richard QuadlingSenior Software DeverloperCommented:

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

ViLeNTAuthor Commented:

If the tree starts off empty, wouldn't such an implementation result in a sequentially linked list?

0

ViLeNTAuthor Commented:

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.

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

ViLeNTAuthor Commented:

Hmm..here is an Array Based way of using Heap Sort