public void trickleUp(int index) {
int parent = (index - 1) / 2;
Node bottom = heapArray[index];
while (index > 0 && heapArray[parent].getKey() < bottom.getKey()) {
heapArray[index] = heapArray[parent]; // move it down
index = parent;
parent = (parent - 1) / 2;
}
heapArray[index] = bottom;
}
public void trickleUp(Node node)
{
Node parent = node.getParent();
while (parent != null &&
parent.getKey() < node.getKey())
{
swapParentWithChild(parent,node);
child = parent;
parent = node.getParent();
}
}
swapParentWithChild(Node parent,Node child)
{
// swapping the actual nodes is quite confusing.
// better is to swap the data and key of the nodes
}
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;
public int size = 0;
/**
* 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);
size++;
} else { // otherwise
// create a node called new Node
Node newNode = new Node(value);
size++;
// 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;
size++;
} else { // otherwise
// insert the new node as the right child
aParent.rightChild = newNode;
size++;
}// end second else
}// 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 trickleUp(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);
}// end if clause
}// end trickleUp()
/**
*This method will traverse through the tree heap and utilize
*the trickleUp method to restore nodes to their proper location
*/
private void heapRestore(Node node) {
int j;
for(j=size/2-1; j >=0; j --)
trickleUp(node);
}//end heapRestore()
}//end treeHeap class
// //////////////////////////////////////////////////////////////////////////////
// //////////////////////////////////////////////////////////////////////////////
If you are experiencing a similar issue, please ask a related question
Title | # Comments | Views | Activity |
---|---|---|---|
best (free) software to access postgres db (java) | 1 | 32 | |
Requested array size exceeds VM limit | 3 | 84 | |
javap not working | 8 | 37 | |
Capture logon name | 13 | 42 |
Join the community of 500,000 technology professionals and ask your questions.
Connect with top rated Experts
14 Experts available now in Live!