Package edu.uci.ics.jung.algorithms.util
Class MapBinaryHeap<T>
- java.lang.Object
-
- java.util.AbstractCollection<T>
-
- edu.uci.ics.jung.algorithms.util.MapBinaryHeap<T>
-
- All Implemented Interfaces:
java.lang.Iterable<T>
,java.util.Collection<T>
,java.util.Queue<T>
public class MapBinaryHeap<T> extends java.util.AbstractCollection<T> implements java.util.Queue<T>
An array-based binary heap implementation of a priority queue, which also provides efficientupdate()
andcontains
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 viaupdate
so that the heap can reposition it efficiently, as necessary.
-
-
Constructor Summary
Constructors Constructor Description MapBinaryHeap()
Creates aMapBinaryHeap
whose heap ordering will be based on the natural ordering of the elements, which must beComparable
.MapBinaryHeap(java.util.Collection<T> c)
Creates aMapBinaryHeap
based on the specified collection whose heap ordering will be based on the natural ordering of the elements, which must beComparable
.MapBinaryHeap(java.util.Collection<T> c, java.util.Comparator<T> comp)
Creates aMapBinaryHeap
based on the specified collection whose heap ordering is based on the ordering of the elements specified byc
.MapBinaryHeap(java.util.Comparator<T> comp)
Creates aMapBinaryHeap
whose heap ordering is based on the ordering of the elements specified byc
.
-
Method Summary
All Methods Instance Methods Concrete Methods Deprecated Methods Modifier and Type Method Description boolean
add(T o)
Insertso
into this collection.void
clear()
boolean
contains(java.lang.Object o)
T
element()
boolean
isEmpty()
Returnstrue
if this collection contains no elements, andfalse
otherwise.java.util.Iterator<T>
iterator()
Returns anIterator
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
pop()
T
remove()
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(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).-
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
-
-
-
-
Constructor Detail
-
MapBinaryHeap
public MapBinaryHeap(java.util.Comparator<T> comp)
Creates aMapBinaryHeap
whose heap ordering is based on the ordering of the elements specified byc
.
-
MapBinaryHeap
public MapBinaryHeap()
Creates aMapBinaryHeap
whose heap ordering will be based on the natural ordering of the elements, which must beComparable
.
-
MapBinaryHeap
public MapBinaryHeap(java.util.Collection<T> c)
Creates aMapBinaryHeap
based on the specified collection whose heap ordering will be based on the natural ordering of the elements, which must beComparable
.
-
-
Method Detail
-
clear
public void clear()
-
add
public boolean add(T o)
Insertso
into this collection.
-
isEmpty
public boolean isEmpty()
Returnstrue
if this collection contains no elements, andfalse
otherwise.
-
peek
public T peek()
Returns the element at the top of the heap; does not alter the heap.- Specified by:
peek
in interfacejava.util.Queue<T>
-
pop
@Deprecated public T pop() throws java.util.NoSuchElementException
Removes the element at the top of this heap, and returns it.- Throws:
java.util.NoSuchElementException
-
size
public int size()
Returns the size of this heap.
-
update
public 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).- Parameters:
o
-
-
contains
public boolean contains(java.lang.Object o)
-
iterator
public java.util.Iterator<T> iterator()
Returns anIterator
that does not support modification of the heap.
-
remove
public boolean remove(java.lang.Object o)
This data structure does not support the removal of arbitrary elements.
-
removeAll
public boolean removeAll(java.util.Collection<?> c)
This data structure does not support the removal of arbitrary elements.
-
retainAll
public boolean retainAll(java.util.Collection<?> c)
This data structure does not support the removal of arbitrary elements.
-
element
public T element() throws java.util.NoSuchElementException
- Specified by:
element
in interfacejava.util.Queue<T>
- Throws:
java.util.NoSuchElementException
-
-