structure
Class SkewHeap

java.lang.Object
  |
  +--structure.SkewHeap
All Implemented Interfaces:
MergeableHeap, PriorityQueue

public class SkewHeap
extends java.lang.Object
implements PriorityQueue, MergeableHeap

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 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.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.isEmpty()){
	    ComparableAssociation p = (ComparableAssociation)programmers.remove();
	    System.out.println(p.getValue() + " is " + p.getKey() + " years old.");
	}
 }
 


Field Summary
protected  int count
          The number of nodes within heap.
protected  BinaryTree root
          The root of the skew heap.
 
Constructor Summary
SkewHeap()
          Constructs an empty priority queue.
 
Method Summary
 void add(java.lang.Comparable value)
          Add a value to the priority queue.
 void clear()
          Remove all the elements from the queue.
 java.lang.Comparable getFirst()
          Fetch lowest valued (highest priority) item from queue.
 boolean isEmpty()
          Determine if the queue is empty.
static void main(java.lang.String[] argv)
           
protected static BinaryTree merge(BinaryTree left, BinaryTree right)
           
 void merge(MergeableHeap otherHeap)
          Merge this heap with another
 java.lang.Comparable remove()
          Returns the minimum value from the queue.
 int size()
          Determine the size of the queue.
 java.lang.String toString()
          Construct a string representation of the heap.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

root

protected BinaryTree root
The root of the skew heap.


count

protected int count
The number of nodes within heap.

Constructor Detail

SkewHeap

public SkewHeap()
Constructs an empty priority queue.

Method Detail

getFirst

public java.lang.Comparable getFirst()
Fetch lowest valued (highest priority) item from queue.

Specified by:
getFirst in interface PriorityQueue
Returns:
The smallest value from queue.

remove

public java.lang.Comparable remove()
Returns the minimum value from the queue.

Specified by:
remove in interface PriorityQueue
Returns:
The minimum value in the queue.

add

public void add(java.lang.Comparable value)
Add a value to the priority queue.

Specified by:
add in interface PriorityQueue
Parameters:
value - The value to be added.

size

public int size()
Determine the size of the queue.

Specified by:
size in interface PriorityQueue
Returns:
The number of elements within the queue.

clear

public void clear()
Remove all the elements from the queue.

Specified by:
clear in interface PriorityQueue

isEmpty

public boolean isEmpty()
Determine if the queue is empty.

Specified by:
isEmpty in interface PriorityQueue
Returns:
True if the queue is empty.

merge

public void merge(MergeableHeap otherHeap)
Merge this heap with another

Specified by:
merge in interface MergeableHeap
Parameters:
otherHeap - Heap to be merged with this heap, otherHeap is destroyed by this operation;

merge

protected static BinaryTree merge(BinaryTree left,
                                  BinaryTree right)

toString

public java.lang.String toString()
Construct a string representation of the heap.

Overrides:
toString in class java.lang.Object
Returns:
The string representing the heap.

main

public static void main(java.lang.String[] argv)