structure
Class SkewHeap

java.lang.Object
  structure.SkewHeap

All Implemented Interfaces:

PriorityQueue

public class SkewHeap
extends java.lang.Object
implements PriorityQueue

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.

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.
protected static BinaryTree	merge(BinaryTree left, BinaryTree right)
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.

Postcondition:

creates 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.

Precondition:

!isEmpty()

Postcondition:

returns the minimum value in priority 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.

Precondition:

!isEmpty()

Postcondition:

returns and removes minimum value from 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.

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

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

Postcondition:

removes all elements from queue

isEmpty

public boolean isEmpty()

Determine if the queue is empty.

Specified by:

isEmpty in interface PriorityQueue

Returns:

True if the queue is empty.

Postcondition:

returns true iff no elements are in queue

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.

Postcondition:

returns string representation of heap