org.jutil.java.collections
Class BinomialHeap

java.lang.Object
  |
  +--org.jutil.java.collections.BinomialHeap

All Implemented Interfaces:

PriorityQueue

public class BinomialHeap

extends java.lang.Object

implements PriorityQueue

A BinomialHeap is a Heap that consists of a forest of Binomial Trees.

Most operations are O(log(n)).

Version:

$Revision: 1.2 $

Author:

Tom Schrijvers

Field Summary

static java.lang.String

CVS_REVISION

Constructor Summary

BinomialHeap(java.util.Comparator comparator)
public behavior

pre comparator != null;

post getComparator() == comparator;
post size() == 0;
Initialize a new BinomialHeap with the given comparator.

BinomialHeap(java.util.Comparator comparator, java.lang.Object element)
public behavior

pre comparator != null;
pre element != null;

post getComparator() == comparator;
post nbExplicitOccurrences(element) == 1;
post size() == 1;
Initialize a new BinomialHeap with the given comparator and element.

Method Summary

void	add(java.lang.Object value) See superclass.
void	clear() See superclass
java.util.Comparator	getComparator() See superclass.
boolean	isEmpty() See superclass.
void	merge(BinomialHeap heap) public behavior pre heap != null; post size() == \old(size()) + \old(heap.size()) post (\forall Object element; ; nbExplicitOccurrences(element) == \old(nbExplicitOccurrences(element)) + \old(heap.nbExplicitOccurrences(element))); post (\forall Object element; ; heap.nbExplicitOccurences(element) == 0);
java.lang.Object	min() See superclass.
int	nbExplicitOccurrences(java.lang.Object element) See superclass.
java.lang.Object	pop() See superclass.
int	size() See superclass.

Methods inherited from class java.lang.Object

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

Field Detail

CVS_REVISION

public static final java.lang.String CVS_REVISION

Constructor Detail

BinomialHeap

public BinomialHeap(java.util.Comparator comparator)

public behavior

pre comparator != null;

post getComparator() == comparator;
post size() == 0;
Initialize a new BinomialHeap with the given comparator.

Parameters:

comparator - The comparator that is used to determine the order of the elements.

BinomialHeap

public BinomialHeap(java.util.Comparator comparator,
                    java.lang.Object element)

public behavior

pre comparator != null;
pre element != null;

post getComparator() == comparator;
post nbExplicitOccurrences(element) == 1;
post size() == 1;
Initialize a new BinomialHeap with the given comparator and element.

Parameters:

comparator - The comparator that is used to determine the order of the elements.

element - The initial element in the new BinomialHeap.

Method Detail

getComparator

public java.util.Comparator getComparator()

See superclass.

Specified by:

getComparator in interface PriorityQueue

add

public void add(java.lang.Object value)

See superclass.

O(log(n))

Specified by:

add in interface PriorityQueue

Following copied from interface: org.jutil.java.collections.PriorityQueue

Parameters:

element - The object to be added.

min

public java.lang.Object min()

See superclass.

O(log(n))

Specified by:

min in interface PriorityQueue

pop

public java.lang.Object pop()

See superclass.

O(log(n))

Specified by:

pop in interface PriorityQueue

merge

public void merge(BinomialHeap heap)

public behavior

pre heap != null;

post size() == \old(size()) + \old(heap.size())
post (\forall Object element; ;
nbExplicitOccurrences(element) == \old(nbExplicitOccurrences(element)) +
\old(heap.nbExplicitOccurrences(element)));
post (\forall Object element; ;
heap.nbExplicitOccurences(element) == 0);

Add all elements in the given BinomialHeap to this heap and empty that heap.

Parameters:

heap - The heap of which the elements are to be added to this heap.

O(log((n))

clear

public void clear()

See superclass

Specified by:

clear in interface PriorityQueue

isEmpty

public boolean isEmpty()

See superclass.

Specified by:

isEmpty in interface PriorityQueue

nbExplicitOccurrences

public int nbExplicitOccurrences(java.lang.Object element)

See superclass.

O(n)

Specified by:

nbExplicitOccurrences in interface PriorityQueue

Following copied from interface: org.jutil.java.collections.PriorityQueue

Parameters:

element - The object of which the number of explicit occurrences is requested.

size

public int size()

See superclass.

Specified by:

size in interface PriorityQueue