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();
}
}
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()
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()
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
class treeHeapApp {
public static void main(String[] args) {
toss(#);
toss(#);
toss(#);
toss(#);
restoreHeap();
} // end main()
} // end class treeHeapApp
private void inOrder(Node localRoot)
{
if(localRoot !=null)
{
inorder(LocalRoot.leftChild);
inOrder(Localroot.rightChild);
}
}
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()
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;
}
If you are experiencing a similar issue, please ask a related question
Title | # Comments | Views | Activity |
---|---|---|---|
custom annotations | 9 | 39 | |
diffSum example | 4 | 37 | |
Problem to error | 4 | 60 | |
Java exception bubble up | 2 | 18 |
Join the community of 500,000 technology professionals and ask your questions.