public class MapBinaryHeap<T> extends AbstractCollection<T> implements Queue<T>
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(Collection<T> 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<T> c,
Comparator<T> 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<T> comp)
Creates a
MapBinaryHeap whose heap ordering
is based on the ordering of the elements specified by comp . |
Modifier and Type | Method and Description |
---|---|
boolean |
add(T o)
Inserts
o into this collection. |
void |
clear() |
boolean |
contains(Object o) |
T |
element() |
boolean |
isEmpty()
Returns
true if this collection contains no elements, and
false otherwise. |
Iterator<T> |
iterator()
Returns an
Iterator that does not support modification
of the heap. |
boolean |
offer(T o) |
T |
peek()
Returns the element at the top of the heap; does not
alter the heap.
|
T |
poll() |
T |
remove() |
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() |
void |
update(T 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
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
addAll, containsAll, equals, hashCode, parallelStream, removeIf, spliterator, stream, toArray, toArray
public MapBinaryHeap(Comparator<T> comp)
MapBinaryHeap
whose heap ordering
is based on the ordering of the elements specified by comp
.comp
- the comparator to use to order elements in the heappublic MapBinaryHeap()
MapBinaryHeap
whose heap ordering
will be based on the natural ordering of the elements,
which must be Comparable
.public MapBinaryHeap(Collection<T> c)
MapBinaryHeap
based on the specified
collection whose heap ordering
will be based on the natural ordering of the elements,
which must be Comparable
.c
- the collection of Comparable
elements to add to the heappublic MapBinaryHeap(Collection<T> c, Comparator<T> comp)
MapBinaryHeap
based on the specified collection
whose heap ordering
is based on the ordering of the elements specified by c
.c
- the collection of elements to add to the heapcomp
- the comparator to use for items in c
public void clear()
clear
in interface Collection<T>
clear
in class AbstractCollection<T>
Collection.clear()
public boolean add(T o)
o
into this collection.add
in interface Collection<T>
add
in interface Queue<T>
add
in class AbstractCollection<T>
public boolean isEmpty()
true
if this collection contains no elements, and
false
otherwise.isEmpty
in interface Collection<T>
isEmpty
in class AbstractCollection<T>
public T peek()
public int size()
size
in interface Collection<T>
size
in class AbstractCollection<T>
public void update(T o)
o
- the object whose key value has been updatedpublic boolean contains(Object o)
contains
in interface Collection<T>
contains
in class AbstractCollection<T>
public Iterator<T> iterator()
Iterator
that does not support modification
of the heap.iterator
in interface Iterable<T>
iterator
in interface Collection<T>
iterator
in class AbstractCollection<T>
public boolean remove(Object o)
remove
in interface Collection<T>
remove
in class AbstractCollection<T>
public boolean removeAll(Collection<?> c)
removeAll
in interface Collection<T>
removeAll
in class AbstractCollection<T>
public boolean retainAll(Collection<?> c)
retainAll
in interface Collection<T>
retainAll
in class AbstractCollection<T>
public T element() throws NoSuchElementException
element
in interface Queue<T>
NoSuchElementException
Copyright © 2015. All rights reserved.