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.- Author:
- Joshua O'Madadhain
-
-
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 bycomp
.
-
Method Summary
All Methods Instance Methods Concrete 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
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()
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 bycomp
.- Parameters:
comp
- the comparator to use to order elements in the heap
-
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
.- Parameters:
c
- the collection ofComparable
elements to add to the heap
-
MapBinaryHeap
public 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
.- Parameters:
c
- the collection of elements to add to the heapcomp
- the comparator to use for items inc
-
-
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>
-
size
public int size()
-
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
- the object whose key value has been updated
-
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
-
-