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.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private class
MapBinaryHeap.ComparableComparator
Comparator used if none is specified in the constructor.
-
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()
private void
initialize(java.util.Comparator<T> comp)
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.private int
lChild(int i)
Returns the index of the left child of the element at indexi
of the heap.boolean
offer(T o)
private int
parent(int i)
Returns the index of the parent of the element at indexi
of the heap.T
peek()
Returns the element at the top of the heap; does not alter the heap.private void
percolateDown(int cur)
Moves the element at positioncur
closer to the bottom of the heap, or returns if no further motion is necessary.private int
percolateUp(int cur, T o)
Moves the elemento
at positioncur
as high as it can go in the heap.T
poll()
private int
rChild(int i)
Returns the index of the right child of the element at indexi
of the heap.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()
private void
swap(int i, int j)
Swaps the positions of the elements at indicesi
andj
of the 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
-
-
-
-
Field Detail
-
heap
private java.util.Vector<T> heap
-
object_indices
private java.util.Map<T,java.lang.Integer> object_indices
-
comp
private java.util.Comparator<T> comp
-
TOP
private static final int TOP
- See Also:
- Constant Field Values
-
-
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
-
initialize
private void initialize(java.util.Comparator<T> comp)
-
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)
-
percolateDown
private void percolateDown(int cur)
Moves the element at positioncur
closer to the bottom of the heap, or returns if no further motion is necessary. Calls itself recursively if further motion is possible.
-
percolateUp
private int percolateUp(int cur, T o)
Moves the elemento
at positioncur
as high as it can go in the heap. Returns the new position of the element in the heap.
-
lChild
private int lChild(int i)
Returns the index of the left child of the element at indexi
of the heap.- Parameters:
i
-- Returns:
- the index of the left child of the element at
index
i
of the heap
-
rChild
private int rChild(int i)
Returns the index of the right child of the element at indexi
of the heap.- Parameters:
i
-- Returns:
- the index of the right child of the element at
index
i
of the heap
-
parent
private int parent(int i)
Returns the index of the parent of the element at indexi
of the heap.- Parameters:
i
-- Returns:
- the index of the parent of the element at index i of the heap
-
swap
private void swap(int i, int j)
Swaps the positions of the elements at indicesi
andj
of the heap.- Parameters:
i
-j
-
-
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
-
-