public class MapBinaryHeap
extends java.util.AbstractCollection
implements java.util.Collection
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 and Description |
---|
MapBinaryHeap()
Creates a
MapBinaryHeap whose heap ordering
will be based on the natural ordering of the elements,
which must be Comparable . |
MapBinaryHeap(java.util.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(java.util.Collection c,
java.util.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(java.util.Comparator comp)
Creates a
MapBinaryHeap whose heap ordering
is based on the ordering of the elements specified by c . |
Modifier and Type | Method and Description |
---|---|
boolean |
add(java.lang.Object o)
Inserts
o into this collection. |
void |
clear() |
boolean |
contains(java.lang.Object o) |
boolean |
isEmpty()
Returns
true if this collection contains no elements, and
false otherwise. |
java.util.Iterator |
iterator()
Returns an
Iterator that does not support modification
of the heap. |
java.lang.Object |
peek()
Returns the element at the top of the heap; does not
alter the heap.
|
java.lang.Object |
pop()
Removes the element at the top of this heap, and returns it.
|
boolean |
remove(java.lang.Object o)
This data structure does not support the removal of arbitrary elements.
|
boolean |
removeAll(java.util.Collection c)
This data structure does not support the removal of arbitrary elements.
|
boolean |
retainAll(java.util.Collection c)
This data structure does not support the removal of arbitrary elements.
|
int |
size()
Returns the size of this heap.
|
void |
update(java.lang.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).
|
addAll, containsAll, toArray, toArray, toString
public MapBinaryHeap(java.util.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(java.util.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(java.util.Collection c, java.util.Comparator comp)
MapBinaryHeap
based on the specified collection
whose heap ordering
is based on the ordering of the elements specified by c
.public void clear()
clear
in interface java.util.Collection
clear
in class java.util.AbstractCollection
Collection.clear()
public boolean add(java.lang.Object o)
o
into this collection.add
in interface java.util.Collection
add
in class java.util.AbstractCollection
public boolean isEmpty()
true
if this collection contains no elements, and
false
otherwise.isEmpty
in interface java.util.Collection
isEmpty
in class java.util.AbstractCollection
public java.lang.Object peek() throws java.util.NoSuchElementException
java.util.NoSuchElementException
public java.lang.Object pop() throws java.util.NoSuchElementException
java.util.NoSuchElementException
public int size()
size
in interface java.util.Collection
size
in class java.util.AbstractCollection
public void update(java.lang.Object o)
o
- public boolean contains(java.lang.Object o)
contains
in interface java.util.Collection
contains
in class java.util.AbstractCollection
Collection.contains(java.lang.Object)
public java.util.Iterator iterator()
Iterator
that does not support modification
of the heap.iterator
in interface java.lang.Iterable
iterator
in interface java.util.Collection
iterator
in class java.util.AbstractCollection
public boolean remove(java.lang.Object o)
remove
in interface java.util.Collection
remove
in class java.util.AbstractCollection
public boolean removeAll(java.util.Collection c)
removeAll
in interface java.util.Collection
removeAll
in class java.util.AbstractCollection
public boolean retainAll(java.util.Collection c)
retainAll
in interface java.util.Collection
retainAll
in class java.util.AbstractCollection