// Implementation of priority queues/heaps using binary trees.
// (c) 1998, 2001 duane a. bailey
package structure;
import java.util.Iterator;
import java.util.Random;
//+interface
/**
* An implementation of a priority queue using skew heaps. Skew heaps
* allow one to construct heaps dynamically without explictly balancing
* the heaps. Main operation is a merge. Most operations execute in
* amortized logarithmic time, but individual operations may take linear
* time to execute in the worst case.
*
*
* Example usage:
*
* To print out a list of programmers sorted by age we could use the following:
*
* public static void main(String[] argv){
* //initialize a new fib heap
* SkewHeap programmers = new {@link #SkewHeap()};
*
* //add programmers and their ages to heap
* //ages current of 7/22/2002
* //add programmers and their ages to heap
* //ages current of 7/22/2002
* programmers.{@link #add(Comparable) add(new ComparableAssociation(new Integer(22), "Evan"))};
* programmers.add(new ComparableAssociation(new Integer(19), "Chris"));
* programmers.add(new ComparableAssociation(new Integer(20), "Shimon"));
* programmers.add(new ComparableAssociation(new Integer(21), "Diane"));
* programmers.add(new ComparableAssociation(new Integer(21), "Lida"));
* programmers.add(new ComparableAssociation(new Integer(20), "Rob"));
* programmers.add(new ComparableAssociation(new Integer(20), "Sean"));
*
* //print out programmers
* while(!programmers.{@link #isEmpty()}){
* ComparableAssociation p = (ComparableAssociation)programmers.{@link #remove()};
* System.out.println(p.getValue() + " is " + p.getKey() + " years old.");
* }
* }
*
* @version $Id: SkewHeap.java,v 1.2 2005/10/18 19:47:23 terescoj Exp $
* @author, 2001 duane a. bailey
*/
public class SkewHeap> implements MergeableHeap
{
//-interface
//+private
//+constructor
/**
* The root of the skew heap.
*/
protected BinaryTree root;
/**
* The number of nodes within heap.
*/
protected int count;
//-private
//+interface
/**
* Constructs an empty priority queue.
*
* @post creates an empty priority queue
*/
public SkewHeap()
//-interface
{
root = BinaryTree.EMPTY;
count = 0;
}
//-constructor
//+interface
//+peek
/**
* Fetch lowest valued (highest priority) item from queue.
*
* @pre !isEmpty()
* @post returns the minimum value in priority queue
*
* @return The smallest value from queue.
*/
public ELTTYPE getFirst()
//-interface
{
return root.value();
}
//-peek
//+interface
//+remove
/**
* Returns the minimum value from the queue.
*
* @pre !isEmpty()
* @post returns and removes minimum value from queue
*
* @return The minimum value in the queue.
*/
public ELTTYPE remove()
//-interface
{
ELTTYPE result = root.value();
root = merge(root.left(),root.right());
count--;
return result;
}
//-remove
//+interface
//+add
/**
* Add a value to the priority queue.
*
* @pre value is non-null comparable
* @post value is added to priority queue
*
* @param value The value to be added.
*/
public void add(ELTTYPE value)
//-interface
{
BinaryTree smallTree = new BinaryTree(value);
root = merge(smallTree,root);
count++;
}
//-add
//+interface
//+size
/**
* Determine the size of the queue.
*
* @post returns number of elements within queue
*
* @return The number of elements within the queue.
*/
public int size()
//-interface
{
return count;
}
//-size
//+interface
//+clear
/**
* Remove all the elements from the queue.
*
* @post removes all elements from queue
*/
public void clear()
//-interface
{
root = BinaryTree.EMPTY;
}
//-clear
//+interface
//+isEmpty
/**
* Determine if the queue is empty.
*
* @post returns true iff no elements are in queue
*
* @return True if the queue is empty.
*/
public boolean isEmpty()
//-interface
{
return size() == 0;
}
//-isEmpty
/**
* Merge this heap with another
*
* @param otherHeap Heap to be merged with this heap, otherHeap
* is destroyed by this operation;
* @post the two heaps are merged and otherHeap is destroyed
*/
public void merge(MergeableHeap otherHeap){
Assert.pre(otherHeap instanceof SkewHeap,
"otherHeap must be instance of SkewHeap");
SkewHeap that = (SkewHeap)otherHeap;
root = merge(this.root, that.root);
that.root = null;
this.count += that.count;
}
//+merge
protected static > BinaryTree merge(BinaryTree left,
BinaryTree right)
{
if (left.isEmpty()) return right;
if (right.isEmpty()) return left;
ELTTYPE leftVal = left.value();
ELTTYPE rightVal = right.value();
BinaryTree result;
if (rightVal.compareTo(leftVal) < 0)
{
result = merge(right,left);
} else {
result = left;
// assertion left side is smaller than right
// left is new root
if (result.left().isEmpty())
{
result.setLeft(right);
} else {
BinaryTree temp = result.right();
result.setRight(result.left());
result.setLeft(merge(temp,right));
}
}
return result;
}
//-merge
/**
* Construct a string representation of the heap.
*
* @post returns string representation of heap
*
* @return The string representing the heap.
*/
public String toString()
{
if (root.isEmpty()) return "";
StringBuffer sb = new StringBuffer();
sb.append("";
}
//+interface
public static void main(String[] argv){
int s1 = 0, s2 = 0, s3 = 1, max = 0;
try{
while(s3 != 198){
Random r = new Random();
max = 0;
s1 = 0;
s2 = 0;
s3 = 0;
SkewHeap t1 = new SkewHeap();
SkewHeap t2 = new SkewHeap();
max = r.nextInt(100);
for(int i=0; i < max; i++){
t1.add(new Integer(r.nextInt(1000)));
}
max = r.nextInt(100);
for(int i=0; i < max; i++){
t2.add(new Integer(r.nextInt(1000)));
}
//System.out.println(t1);
//System.out.println(t2);
s1 = t1.size();
s2 = t2.size();
t1.merge(t2);
s3 = t1.size();
//System.out.println(t1);
Assert.condition(s1+s2==s3,"Trees merge with right sizes.");
System.out.println(s1 + " : " + s2 + " : " + s3);
}
} catch (NullPointerException e) {
System.out.println(s1 + " : " + s2 + " : " + s3);
}
}
}
//-interface