drasys.or.cont
Class BinomialHeap

java.lang.Object
  |
  +--drasys.or.cont.BinomialHeap

public class BinomialHeap

extends java.lang.Object

implements PriorityQueueI, java.io.Serializable

A binomial heap implementation of a priority queue.

References:

Introduction to Algorithms
    Thomas H. Cormen, et al / Hardcover / Published 1990

See Also:

BinaryHeap, PriorityQueue, Serialized Form

Constructor Summary

BinomialHeap(CompareI compare)

 

Method Summary
void	changePriority(PairI pelement, java.lang.Object priority)           Change the priority of a element in the queue.
boolean	check()           Check the integrity of the internal data structures.
java.util.Enumeration	elements()           Get an enumerator to access all the elements in random order.
void	ensureCapacity(int capacity)           This is not needed with this queue and has no effect.
PairI	getHead()           Access the next element in the queue and leave the entry in the queue.
PairI	insert(java.lang.Object priority)
PairI	insert(java.lang.Object priority, java.lang.Object object)           Insert a new element into the queue, with separate priority and value objects.
PairI	popHead()           Access the next element in the queue and remove the entry from the queue.
void	removeAllElements()           Remove all elements from the queue.
void	setCompare(CompareI compare)           Sets a new comparison function.
int	size()

 

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

 

Constructor Detail

BinomialHeap

public BinomialHeap(CompareI compare)

size

public int size()

Specified by:

size in interface PriorityQueueI

Returns:

The number of elements in the heap.

See Also:

PriorityQueueI

elements

public java.util.Enumeration elements()

Description copied from interface: PriorityQueueI

Get an enumerator to access all the elements in random order.

Specified by:

elements in interface PriorityQueueI

See Also:

PriorityQueueI

removeAllElements

public void removeAllElements()

Description copied from interface: PriorityQueueI

Remove all elements from the queue.

Specified by:

removeAllElements in interface PriorityQueueI

See Also:

PriorityQueueI

ensureCapacity

public void ensureCapacity(int capacity)

This is not needed with this queue and has no effect.

Specified by:

ensureCapacity in interface PriorityQueueI

getHead

public PairI getHead()

Description copied from interface: PriorityQueueI

Access the next element in the queue and leave the entry in the queue.

Specified by:

getHead in interface PriorityQueueI

See Also:

PriorityQueueI

popHead

public PairI popHead()

Description copied from interface: PriorityQueueI

Access the next element in the queue and remove the entry from the queue.

Specified by:

popHead in interface PriorityQueueI

See Also:

PriorityQueueI

insert

public PairI insert(java.lang.Object priority)

See Also:

PriorityQueueI

insert

public PairI insert(java.lang.Object priority,
                    java.lang.Object object)

Description copied from interface: PriorityQueueI

Insert a new element into the queue, with separate priority and value objects.

Specified by:

insert in interface PriorityQueueI

See Also:

PriorityQueueI

setCompare

public void setCompare(CompareI compare)

Sets a new comparison function. This will empty the queue if it contains any objects.

Specified by:

setCompare in interface PriorityQueueI

changePriority

public void changePriority(PairI pelement,
                           java.lang.Object priority)
                    throws InvalidPriorityException

Description copied from interface: PriorityQueueI

Change the priority of a element in the queue.

Specified by:

changePriority in interface PriorityQueueI

Throws:

InvalidPriorityException - If the new priority is not higher in order.

See Also:

PriorityQueueI

check

public boolean check()

Description copied from interface: PriorityQueueI

Check the integrity of the internal data structures.

Specified by:

check in interface PriorityQueueI

See Also:

PriorityQueueI