With monday.comâ€™s project management tool, you can see what everyone on your team is working in a single glance. Its intuitive dashboards are customizable, so you can create systems that work for you.

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

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

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

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

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

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.

However, I am stuck as to how to do this.

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?

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.

The heap doesn't know when how many items you've got to toss in.

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
```

"An inorder traversal of a binary search tree will cause all the nodes to be visited in ascending order"

"The simplest way to carry out traversal is the use of recursion"

1. Call itself to traverse the node's left subtree

2. Visit the node

3. Call itself to traverse the node's right subtree

Does this help?

```
private void inOrder(Node localRoot)
{
if(localRoot !=null)
{
inorder(LocalRoot.leftChild);
inOrder(Localroot.rightChild);
}
}
```

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

Unless you know a mid point in the values, you will end up with a very heavily one-sided tree?

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.

Does this sound logical?

http://en.wikipedia.org/wiki/Heapsort goes into some detail.

Could we modify this to be tree-based?

http://www.ehow.com/how_2094984_use-heapsort-java.html?ref=fuel&utm_source=yahoo&utm_medium=ssp&utm_campaign=yssp_art

Just have to go through and transition from array to tree.

```
This is Array:
This is Tree-Based
void swapValues(Node p, Node q) {
E temp = p.value;
p.value = q.value;
q.value = temp;
}
This is Array-Based
public static final void swapReferences( Object [ ] a, int index1, int index2 )
{
Object tmp = a[ index1 ];
a[ index1 ] = a[ index2 ];
a[ index2 ] = tmp;
}
```

All Courses

From novice to tech pro — start learning today.