org.jutil.java.collections
Class BasicBinomialHeap

java.lang.Object
  |
  +--org.jutil.java.collections.AbstractDispenser
        |
        +--org.jutil.java.collections.AbstractPriorityQueue
              |
              +--org.jutil.java.collections.BasicBinomialHeap

All Implemented Interfaces:

Dispenser, PriorityQueue

class BasicBinomialHeap

extends AbstractPriorityQueue

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

Most operations are O(log(n)).

Fields inherited from class org.jutil.java.collections.AbstractPriorityQueue

CVS_REVISION

 

Constructor Summary

BasicBinomialHeap(java.util.Comparator comparator)           Initialize a new BasicBinomialHeap with the given comparator.

BasicBinomialHeap(java.util.Comparator comparator, java.lang.Object element)           Initialize a new BasicBinomialHeap with the given comparator and element.

 

Method Summary
protected  void	addImpl(java.lang.Object value)           See superclass. O(log(n))
void	clear()           See superclass
java.util.Comparator	getComparator()           See superclass.
void	merge(BasicBinomialHeap heap)           Add all elements in the given BasicBinomialHeap to this heap and empty that heap.
java.lang.Object	min()           See superclass. O(log(n))
int	nbExplicitOccurrences(java.lang.Object element)           See superclass. O(n)
java.lang.Object	pop()           See superclass. O(log(n))
int	size()           See superclass.

 

Methods inherited from class org.jutil.java.collections.AbstractPriorityQueue

getNext, removeNext

 

Methods inherited from class org.jutil.java.collections.AbstractDispenser

add, isEmpty

 

Methods inherited from class java.lang.Object

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

 

Methods inherited from interface org.jutil.java.collections.Dispenser

add, isEmpty

 

Constructor Detail

BasicBinomialHeap

public BasicBinomialHeap(java.util.Comparator comparator)

Initialize a new BasicBinomialHeap with the given comparator.

Parameters:

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

Specifications:

public behavior
requires comparator != null;
ensures getComparator() == comparator;
ensures size() == 0;

BasicBinomialHeap

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

Initialize a new BasicBinomialHeap 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 BasicBinomialHeap.

Specifications:

public behavior
requires comparator != null;
requires element != null;
ensures getComparator() == comparator;
ensures nbExplicitOccurrences(element) == 1;
ensures size() == 1;

getComparator

public java.util.Comparator getComparator()

See superclass.

Specifications inherited from overridden method in interface PriorityQueue:

public behavior
ensures \result != null;

addImpl

protected void addImpl(java.lang.Object value)

See superclass.

O(log(n))

Specifications inherited from overridden method in class AbstractDispenser:

public behavior
requires item != null;
ensures nbExplicitOccurrences(item) == \old(nbExplicitOccurrences(item))+1;

min

public java.lang.Object min()

See superclass.

O(log(n))

Specifications inherited from overridden method in interface PriorityQueue:

public behavior
requires !isEmpty();
ensures nbExplicitOccurrences(\result ) > 0;
ensures ( \forall Object o; nbExplicitOccurrences(o) > 0; ExtendedComparator.ensureExtended(getComparator()).notGreater(o,\result ));

pop

public java.lang.Object pop()

See superclass.

O(log(n))

Specifications inherited from overridden method in interface PriorityQueue:

public behavior
requires !isEmpty();
ensures \result == \old(min());
ensures nbExplicitOccurrences(\result ) == \old(nbExplicitOccurrences(getNext()))-1;

merge

public void merge(BasicBinomialHeap heap)

Add all elements in the given BasicBinomialHeap 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))

Specifications:

public behavior
requires heap != null;
ensures size() == \old(size())+\old(heap.size());
ensures ( \forall Object element; ; nbExplicitOccurrences(element) == \old(nbExplicitOccurrences(element))+\old(heap.nbExplicitOccurrences(element)));
ensures ( \forall Object element; ; heap.nbExplicitOccurrences(element) == 0);

clear

public void clear()

See superclass

nbExplicitOccurrences

public int nbExplicitOccurrences(java.lang.Object element)

See superclass.

O(n)

Specifications inherited from overridden method in interface Dispenser:

public behavior
ensures \result >= 0;

size

public int size()

See superclass.

Specifications inherited from overridden method in interface Dispenser:

public behavior
ensures \result == ( \sum Object item; ; nbExplicitOccurrences(item));