edu.uci.ics.jung.utils
Class MapBinaryHeap

java.lang.Object
  extended by java.util.AbstractCollection
      extended by edu.uci.ics.jung.utils.MapBinaryHeap
All Implemented Interfaces:
Iterable, Collection

public class MapBinaryHeap
extends AbstractCollection
implements Collection

An array-based binary heap implementation of a priority queue, which also provides efficient update() and contains operations. It contains extra infrastructure (a hash table) to keep track of the position of each element in the array; thus, if the key value of an element changes, it may be "resubmitted" to the heap via update so that the heap can reposition it efficiently, as necessary.

Author:
Joshua O'Madadhain

Constructor Summary
MapBinaryHeap()
          Creates a MapBinaryHeap whose heap ordering will be based on the natural ordering of the elements, which must be Comparable.
MapBinaryHeap(Collection c)
          Creates a MapBinaryHeap based on the specified collection whose heap ordering will be based on the natural ordering of the elements, which must be Comparable.
MapBinaryHeap(Collection c, Comparator comp)
          Creates a MapBinaryHeap based on the specified collection whose heap ordering is based on the ordering of the elements specified by c.
MapBinaryHeap(Comparator comp)
          Creates a MapBinaryHeap whose heap ordering is based on the ordering of the elements specified by c.
 
Method Summary
 boolean add(Object o)
          Inserts o into this collection.
 void clear()
           
 boolean contains(Object o)
           
 boolean isEmpty()
          Returns true if this collection contains no elements, and false otherwise.
 Iterator iterator()
          Returns an Iterator that does not support modification of the heap.
 Object peek()
          Returns the element at the top of the heap; does not alter the heap.
 Object pop()
          Removes the element at the top of this heap, and returns it.
 boolean remove(Object o)
          This data structure does not support the removal of arbitrary elements.
 boolean removeAll(Collection c)
          This data structure does not support the removal of arbitrary elements.
 boolean retainAll(Collection c)
          This data structure does not support the removal of arbitrary elements.
 int size()
          Returns the size of this heap.
 void update(Object o)
          Informs the heap that this object's internal key value has been updated, and that its place in the heap may need to be shifted (up or down).
 
Methods inherited from class java.util.AbstractCollection
addAll, containsAll, toArray, toArray, toString
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface java.util.Collection
addAll, containsAll, equals, hashCode, toArray, toArray
 

Constructor Detail

MapBinaryHeap

public MapBinaryHeap(Comparator comp)
Creates a MapBinaryHeap whose heap ordering is based on the ordering of the elements specified by c.


MapBinaryHeap

public MapBinaryHeap()
Creates a MapBinaryHeap whose heap ordering will be based on the natural ordering of the elements, which must be Comparable.


MapBinaryHeap

public MapBinaryHeap(Collection c)
Creates a MapBinaryHeap based on the specified collection whose heap ordering will be based on the natural ordering of the elements, which must be Comparable.


MapBinaryHeap

public MapBinaryHeap(Collection c,
                     Comparator comp)
Creates a MapBinaryHeap based on the specified collection whose heap ordering is based on the ordering of the elements specified by c.

Method Detail

clear

public void clear()
Specified by:
clear in interface Collection
Overrides:
clear in class AbstractCollection
See Also:
Collection.clear()

add

public boolean add(Object o)
Inserts o into this collection.

Specified by:
add in interface Collection
Overrides:
add in class AbstractCollection

isEmpty

public boolean isEmpty()
Returns true if this collection contains no elements, and false otherwise.

Specified by:
isEmpty in interface Collection
Overrides:
isEmpty in class AbstractCollection

peek

public Object peek()
            throws NoSuchElementException
Returns the element at the top of the heap; does not alter the heap.

Throws:
NoSuchElementException

pop

public Object pop()
           throws NoSuchElementException
Removes the element at the top of this heap, and returns it.

Throws:
NoSuchElementException

size

public int size()
Returns the size of this heap.

Specified by:
size in interface Collection
Specified by:
size in class AbstractCollection

update

public void update(Object o)
Informs the heap that this object's internal key value has been updated, and that its place in the heap may need to be shifted (up or down).

Parameters:
o -

contains

public boolean contains(Object o)
Specified by:
contains in interface Collection
Overrides:
contains in class AbstractCollection
See Also:
Collection.contains(java.lang.Object)

iterator

public Iterator iterator()
Returns an Iterator that does not support modification of the heap.

Specified by:
iterator in interface Iterable
Specified by:
iterator in interface Collection
Specified by:
iterator in class AbstractCollection

remove

public boolean remove(Object o)
This data structure does not support the removal of arbitrary elements.

Specified by:
remove in interface Collection
Overrides:
remove in class AbstractCollection

removeAll

public boolean removeAll(Collection c)
This data structure does not support the removal of arbitrary elements.

Specified by:
removeAll in interface Collection
Overrides:
removeAll in class AbstractCollection

retainAll

public boolean retainAll(Collection c)
This data structure does not support the removal of arbitrary elements.

Specified by:
retainAll in interface Collection
Overrides:
retainAll in class AbstractCollection