org.jutil.java.collections
Class BinomialHeap

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

All Implemented Interfaces:

Dispenser, PriorityQueue

public class BinomialHeap

extends AbstractPriorityQueue

A BinomialHeap is a Heap with most of its operations O(1) or O(log(1)).

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

CVS_REVISION

 

Constructor Summary

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

BinomialHeap(java.util.Comparator comparator, java.lang.Object root)           Initialize a new BinomialHeap 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(BinomialHeap heap)           Add all elements in the given BinomialHeap to this heap and empty that heap.
java.lang.Object	min()           See superclass. O(1)
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

BinomialHeap

public BinomialHeap(java.util.Comparator comparator)

Initialize a new BinomialHeap 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;

BinomialHeap

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

Initialize a new BinomialHeap with the given comparator and element.

Parameters:

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

root - The initial element in the new BinomialHeap.

Specifications:

public behavior
requires comparator != null;
requires root != null;
ensures getComparator() == comparator;
ensures nbExplicitOccurrences(root) == 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(1)

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(BinomialHeap heap)

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))

Specifications:

public behavior
requires heap != null;
requires ( \forall Object a, b; heap.nbExplicitOccurrences(a) > 0&&heap.nbExplicitOccurrences(b) > 0; getComparator().compare(a,b) == 0||heap.getComparator().compare(a,b) == 0||getComparator().compare(a,b)*heap.getComparator().compare(a,b) > 0);
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));