|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectjava.util.AbstractCollection
edu.uci.ics.jung.utils.MapBinaryHeap
public class MapBinaryHeap
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.
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 |
---|
public MapBinaryHeap(Comparator comp)
MapBinaryHeap
whose heap ordering
is based on the ordering of the elements specified by c
.
public MapBinaryHeap()
MapBinaryHeap
whose heap ordering
will be based on the natural ordering of the elements,
which must be Comparable
.
public MapBinaryHeap(Collection c)
MapBinaryHeap
based on the specified
collection whose heap ordering
will be based on the natural ordering of the elements,
which must be Comparable
.
public MapBinaryHeap(Collection c, Comparator comp)
MapBinaryHeap
based on the specified collection
whose heap ordering
is based on the ordering of the elements specified by c
.
Method Detail |
---|
public void clear()
clear
in interface Collection
clear
in class AbstractCollection
Collection.clear()
public boolean add(Object o)
o
into this collection.
add
in interface Collection
add
in class AbstractCollection
public boolean isEmpty()
true
if this collection contains no elements, and
false
otherwise.
isEmpty
in interface Collection
isEmpty
in class AbstractCollection
public Object peek() throws NoSuchElementException
NoSuchElementException
public Object pop() throws NoSuchElementException
NoSuchElementException
public int size()
size
in interface Collection
size
in class AbstractCollection
public void update(Object o)
o
- public boolean contains(Object o)
contains
in interface Collection
contains
in class AbstractCollection
Collection.contains(java.lang.Object)
public Iterator iterator()
Iterator
that does not support modification
of the heap.
iterator
in interface Iterable
iterator
in interface Collection
iterator
in class AbstractCollection
public boolean remove(Object o)
remove
in interface Collection
remove
in class AbstractCollection
public boolean removeAll(Collection c)
removeAll
in interface Collection
removeAll
in class AbstractCollection
public boolean retainAll(Collection c)
retainAll
in interface Collection
retainAll
in class AbstractCollection
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |