I'm trying to figure out how to merge to full, complete binary heaps if their heights differ by more than 1.
For example, a heap with 7 elements merged with a heap with 31 elements, etc.
Here's my Java Code for the problem. I can't quite figure out what I'm supposed to do. I made a theory but I'm not sure, even after doing some research. And we were told that changing the internal structure before merging counts against our runtime.
/**
* Answer to problema 21.17 a, b and c
*
* Insertion and Deletion take slightly more time than a normal array-based
* binary heap, however merging of two full/complete heaps can be done in
* better timing than array-based ones.
*
* @author Intrade
*/
public class ExplicitLinkBinaryHeap<T extends Comparable<? super T>>{
public static void main(String... args){
ExplicitLinkBinaryHeap<Integer> elbh = new ExplicitLinkBinaryHeap<Integer>();
ExplicitLinkBinaryHeap<Integer> elbh2 = new ExplicitLinkBinaryHeap<Integer>();
final java.util.Random rgen = new java.util.Random();
for(int i = 0; i < 7; i++){
elbh.add(rgen.nextInt(40) + 5);
elbh2.add(rgen.nextInt(99) + 50);
}
System.out.println(elbh);
System.out.println(elbh2);
ExplicitLinkBinaryHeap<Integer> mergedTreeA = mergeA(elbh, elbh2/*, 1*/);
System.out.println("\nThe result of these two trees merged via method a is...\n");
System.out.println(mergedTreeA);
System.out.println("\n\n");
elbh = new ExplicitLinkBinaryHeap<Integer>();
elbh2 = new ExplicitLinkBinaryHeap<Integer>();
for(int i = 0; i < 7; i++){
elbh.add(rgen.nextInt(40) + 5);
if(i % 2 == 1)
elbh2.add(rgen.nextInt(99) + 50);
}
System.out.println(elbh);
System.out.println(elbh2);
ExplicitLinkBinaryHeap<Integer> mergedTreeB = mergeB(elbh, elbh2/*, 1*/);
System.out.println("\nThe result of these two trees merged via method b is...\n");
System.out.println(mergedTreeB);
System.out.println("\n\n");
elbh = new ExplicitLinkBinaryHeap<Integer>();
elbh2 = new ExplicitLinkBinaryHeap<Integer>();
for(int i = 0; i < 7; i++)
elbh.add(rgen.nextInt(40) + 5);
for(int i = 0; i < 31; i++)
elbh2.add(rgen.nextInt(99) + 50);
System.out.println(elbh);
System.out.println(elbh2);
ExplicitLinkBinaryHeap<Integer> mergedTreeC = mergeC(elbh, elbh2/*, 1*/);
System.out.println("\nThe result of these two trees merged via method c is...\n");
System.out.println(mergedTreeC);
System.out.println("\n\n");
}
// A class to help us with the internal structuring
private class Node implements Comparable< Node >{
Node leftNode, rightNode, parentNode;
T value;
public Node(T value){
this.value = value;
}
public Node(T value, Node parent){
this(value);
this.parentNode = parent;
}
@Override
public int compareTo(Node other){
return value.compareTo(other.value);
}
/**
* Returns the toString() of the value this Node holds
*/
@Override
public String toString(){
return "[ " + value.toString() + " ]";
}
}
private enum Direction{
LEFT,
RIGHT
};
private Node root = null; // the root
private int nodeCount; // how many elements are in the heap
/**
* Constructs the binary heap
*/
public ExplicitLinkBinaryHeap(){
nodeCount = 0;
}
/**
* Problem 21.17a, merging two heaps in O(logN) time when they have the same amount of nodes,
* and are full, complete binary heaps (full/complete requirements are needed for these kind
* of merges)
*
* Returns the merged result-tree of lhs and rhs
*
* Assumption: If the two trees are equal in structure/size and height, then we can merge the
* two by simply adding a dummy node as the root, and delete it from the tree.
*/
public static <E extends Comparable<? super E>> ExplicitLinkBinaryHeap<E>
mergeA(ExplicitLinkBinaryHeap<E> lhs, ExplicitLinkBinaryHeap<E> rhs/*, E dummyValue*/){
ExplicitLinkBinaryHeap<E> resultTree = new ExplicitLinkBinaryHeap<E>();
resultTree.add(lhs.getMin()/*dummyValue*/);
resultTree.nodeCount += lhs.nodeCount + rhs.nodeCount; // to ensure operations work properly during deletion
resultTree.root.leftNode = lhs.root;
resultTree.root.rightNode = rhs.root;
resultTree.removeMin(); // O(logN)
return resultTree;
}
/**
* Problem 21.17b, merging two heaps in O(logN) time when they have differing heights (by 1)
*
* Returns the merged result-tree of lhs and rhs
*
* Assumption: This time we can't simply just make a dummy node and delete. Now we have to consider
* which tree is the larger one, swap the value of the dummy with the largest-tree's root value
* then percolate down the larger tree
*/
public static <E extends Comparable<? super E>> ExplicitLinkBinaryHeap<E>
mergeB(ExplicitLinkBinaryHeap<E> lhs, ExplicitLinkBinaryHeap<E> rhs/*, E dummyValue*/){
ExplicitLinkBinaryHeap<E> resultTree = new ExplicitLinkBinaryHeap<E>();
resultTree.add(lhs.getMin()/*dummyValue*/); // the tree is empty, so this is O(1)
resultTree.nodeCount += lhs.nodeCount + rhs.nodeCount; // to ensure operations work properly during deletion
if( !(rhs.nodeCount > lhs.nodeCount) ){
resultTree.root.leftNode = lhs.root;
resultTree.root.rightNode = rhs.root;
}else{
resultTree.root.leftNode = rhs.root;
resultTree.root.rightNode = lhs.root;
}
E elem = resultTree.root.value;
resultTree.root.value = resultTree.root.leftNode.value;
resultTree.root.leftNode.value = elem;
E fake = (rhs.nodeCount > lhs.nodeCount) ? rhs.removeMin() : lhs.removeMin(); // O(logN)
resultTree.percolateDown(resultTree.root); // O(logN)
// O(logN + logN), or O(2logN) which is close enough to O(logN), though we can probably
// do better...
return resultTree;
}
/**
* Problem 21.17c, merging two heaps in O(log^2(N)) time when they have any differing height
*
* Returns the merged result-tree of lhs and rhs
*
* Assumption: I honestly don't know, even after considering the merge algorithm from
* http://users.informatik.uni-halle.de/~jopsi/dinf503/heap_merge.gif
*
* Assumption 2: It may be possible to, somehow, implement this algorithm in O(log^2(N))
* if the data structure was a heap linkedlist? Concatenate the structures and percolate
* down each node? Easier said than done obviously, because the concatenation would have
* to take little time...
*/
public static <E extends Comparable<? super E>> ExplicitLinkBinaryHeap<E>
mergeC(ExplicitLinkBinaryHeap<E> lhs, ExplicitLinkBinaryHeap<E> rhs){
if(lhs.nodeCount == rhs.nodeCount){
return mergeA(lhs, rhs);
}else if( ((lhs.nodeCount * 2) + 1) == rhs.nodeCount ||
((lhs.nodeCount - 1)/2) == rhs.nodeCount ){
return mergeB(lhs, rhs);
}else{
// Probably O(NlogN), not sure.. it depends on what we consider to be N
if(lhs.nodeCount < rhs.nodeCount){
while(lhs.getMin() != null) rhs.add(lhs.removeMin());
return rhs;
}else{
while(rhs.getMin() != null) lhs.add(rhs.removeMin());
return lhs;
}
}
}
/**
* Adds an item to this BinaryHeap. This BinaryHeap does not negate repeats
*
* This binary heap does not accept null values
*/
public boolean add(T x){
if(x != null){
if(root == null){
root = new Node(x);
}else{
Node parent = getNode( (nodeCount - 1)/2 );
Node xNode = (parent.leftNode == null) ?
(parent.leftNode = new Node(x)) :
(parent.rightNode = new Node(x));
xNode.parentNode = parent;
Node temp = xNode;
try{
// if the parent isn't null and if the node added is less than its parent
// we need to recursively push the value
while(temp.parentNode != null && temp.compareTo(temp.parentNode) < 0){
// standard swap
{
T elem = temp.value;
temp.value = temp.parentNode.value;
temp.parentNode.value = elem;
}
temp = temp.parentNode;
}
}catch(Exception e){} // filtering null reads
}
nodeCount++;
return true;
}else return false;
}
/**
* Gets the minimum value from this tree, without removing it
*/
public T getMin(){
return (root != null) ? root.value : null;
}
/**
* Removes the minimum value from this binary heap
*
* does nothing and returns null if the root is null
*/
public T removeMin(){
if(root != null){
T value = root.value;
Node lastNode = getNode(nodeCount - 1); // gets the last node
root.value = lastNode.value; // assigning the root with the last node's value
//perc the root
percolateDown(root);
// remove the last node from the tree if it has a parent
if(lastNode.parentNode != null){
if(lastNode.parentNode.rightNode != null)
lastNode.parentNode.rightNode = null;
else lastNode.parentNode.leftNode = null;
}else root = null; // is the root if no parent exists
nodeCount--;
return value;
}else return null;
}
/*
* Percs the value down the heap until it finds a suitable "stop"
*/
private void percolateDown(Node holeRoot){
// if there is a child node to, potentially trade values with, we can percolate down
if(holeRoot.leftNode != null || holeRoot.rightNode != null){
// only left node should exist
if(holeRoot.rightNode == null){
if(holeRoot.leftNode.compareTo(holeRoot) < 0){ // if the left node is smaller than the node
// perform a swap and perc the leftNode
{
T t = holeRoot.value;
holeRoot.value = holeRoot.leftNode.value;
holeRoot.leftNode.value = t;
}
percolateDown(holeRoot.leftNode);
}
}else{
// get the minimum
Node minNode = (holeRoot.leftNode.compareTo(holeRoot.rightNode) <= 0) ?
holeRoot.leftNode : holeRoot.rightNode;
if(minNode.compareTo(holeRoot) < 0){ // if the min node is smaller than the node
// perform a swap and perc the minNode
{
T t = holeRoot.value;
holeRoot.value = minNode.value;
minNode.value = t;
}
percolateDown(minNode);
}
}
}else return;
}
/**
* Gets the node if it exists
*/
protected Node getNode(int index){
// the node cant exist if this is true
if(index < 0 || index > nodeCount - 1)
return null;
else if(index == 0)
return root;
else{
Node temp = root;
// a path that tells us where to go - its size depends on how many elements are in the tree
// a back-tracking technique
Direction path[] = new Direction[ (int)(Math.log(index + 1)/Math.log(2)) ];
for(int i = path.length - 1, j = index; i >= 0; i--){
if( j % 2 == 1 ){ // if an odd number
path[i] = Direction.LEFT;
j = (j - 1)/2;
}else{ // if an even number
path[i] = Direction.RIGHT;
j = (j - 2)/2;
}
}
// now to unwind the backtracked path and use it to traverse the tree
for(Direction element : path)
temp = (element == Direction.LEFT) ? temp.leftNode : temp.rightNode;
return temp;
}
}
/*
* Recursively traverses the nodes, storing its contents
* and its children's contents if they aren't null
*/
private String nodeValue(Node x, String tabValue){
String result = "";
if(x.rightNode != null)
result += nodeValue(x.rightNode, tabValue + "\t") + "\n";
result += tabValue + x/*.value*/ + "\n";
if(x.leftNode != null)
result += nodeValue(x.leftNode, tabValue + "\t") + "\n";
return result;
}
/**
* Prints out the internal structure of this Heap
*/
@Override
public String toString(){
if(root != null)
return nodeValue(root, "");
else return "";
}
}