MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.
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 8 lambda expresssions exception handling | 3 | 88 | |
Opening PDF on button click and fill new document | 2 | 35 | |
Why my table column Id is not passed to java object? | 4 | 38 | |
mysql jsp example issue | 32 | 32 |
Join the community of 500,000 technology professionals and ask your questions.
Connect with top rated Experts
15 Experts available now in Live!