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);
} else { //otherwise
//create a node called new Node
Node newNode = new Node(value);
//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;
} else { //otherwise
//insert the new node as the right child
aParent.rightChild = newNode;
}//end second else
}//end first else
return true;
}//end toss()
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;
/**
* 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);
} else { //otherwise
//create a node called new Node
Node newNode = new Node(value);
//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;
} else { //otherwise
//insert the new node as the right child
aParent.rightChild = newNode;
}//end second else
restoreHeap(newNode);
}//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 restoreHeap(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);
//and restore the heap to heap specifications
restoreHeap(node.parent);
}// end if clause
}// end restoreHeap()
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
If you are experiencing a similar issue, please ask a related question
Title | # Comments | Views | Activity |
---|---|---|---|
Java passing arguments (type error) | 2 | 48 | |
Image decoding from Camera | 3 | 72 | |
Spring Framework HTTPSession management | 1 | 24 | |
xampp tool | 12 | 28 |
Join the community of 500,000 technology professionals and ask your questions.
Connect with top rated Experts
16 Experts available now in Live!