structure5
Class SkewHeap<E extends java.lang.Comparable<E>>

java.lang.Object
  structure5.SkewHeap<E>

All Implemented Interfaces:

MergeableHeap<E>, PriorityQueue<E>

public class SkewHeap<E extends java.lang.Comparable<E>>
extends java.lang.Object
implements MergeableHeap<E>

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<E>	EMPTY
protected BinaryTree<E>	root The root of the skew heap.

Constructor Summary

SkewHeap()
Constructs an empty priority queue.

Method Summary

void	add(E value) Add a value to the priority queue.
void	clear() Remove all the elements from the queue.
E	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 <E extends java.lang.Comparable<E>> BinaryTree<E>	merge(BinaryTree<E> left, BinaryTree<E> right)
void	merge(MergeableHeap<E> otherHeap) Merge this heap with another
E	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<E extends java.lang.Comparable<E>> root

The root of the skew heap.

EMPTY

protected final BinaryTree<E extends java.lang.Comparable<E>> EMPTY

count

protected int count

The number of nodes within heap.

Constructor Detail

SkewHeap

public SkewHeap()

Constructs an empty priority queue.

Postcondition:

creates an empty priority queue

Method Detail

getFirst

public E getFirst()

Fetch lowest valued (highest priority) item from queue.

Specified by:

getFirst in interface PriorityQueue<E extends java.lang.Comparable<E>>

Returns:

The smallest value from queue.

Precondition:

!isEmpty()

Postcondition:

returns the minimum value in priority queue

remove

public E remove()

Returns the minimum value from the queue.

Specified by:

remove in interface PriorityQueue<E extends java.lang.Comparable<E>>

Returns:

The minimum value in the queue.

Precondition:

!isEmpty()

Postcondition:

returns and removes minimum value from queue

add

public void add(E value)

Add a value to the priority queue.

Specified by:

add in interface PriorityQueue<E extends java.lang.Comparable<E>>

Parameters:

value - The value to be added.

Precondition:

value is non-null comparable

Postcondition:

value is added to priority queue

size

public int size()

Determine the size of the queue.

Specified by:

size in interface PriorityQueue<E extends java.lang.Comparable<E>>

Returns:

The number of elements within the queue.

Postcondition:

returns number of elements within queue

clear

public void clear()

Remove all the elements from the queue.

Specified by:

clear in interface PriorityQueue<E extends java.lang.Comparable<E>>

Postcondition:

removes all elements from queue

isEmpty

public boolean isEmpty()

Determine if the queue is empty.

Specified by:

isEmpty in interface PriorityQueue<E extends java.lang.Comparable<E>>

Returns:

True if the queue is empty.

Postcondition:

returns true iff no elements are in queue

merge

public void merge(MergeableHeap<E> otherHeap)

Merge this heap with another

Specified by:

merge in interface MergeableHeap<E extends java.lang.Comparable<E>>

Parameters:

otherHeap - Heap to be merged with this heap, otherHeap is destroyed by this operation;

Postcondition:

the two heaps are merged and otherHeap is destroyed

merge

protected static <E extends java.lang.Comparable<E>> BinaryTree<E> merge(BinaryTree<E> left,
                                                                         BinaryTree<E> 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.

Postcondition:

returns string representation of heap

main

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