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.

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

That should fix your error 2. I will lookover your other erros

0

Benefit from a mission critical IT monitoring with Monitis Premium or get it FREE for your entry level monitoring needs.
-Over 200,000 users
-More than 300,000 websites monitored
-Used in 197 countries
-Recommended by 98% of users

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

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.

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.

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

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

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.

Is this a way we could possible get an expert in here who specializes in java? I appreciate your time.

0

Featured Post

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilationâ€¦

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.

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 â€¦