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:
Iterable<T>
,Collection<T>
,Queue<T>
An array-based binary heap implementation of a priority queue,
which also provides
efficient
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.-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate class
Comparator used if none is specified in the constructor. -
Field Summary
Fields -
Constructor Summary
ConstructorsConstructorDescriptionCreates aMapBinaryHeap
whose heap ordering will be based on the natural ordering of the elements, which must beComparable
.MapBinaryHeap
(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
(Collection<T> c, Comparator<T> comp) Creates aMapBinaryHeap
based on the specified collection whose heap ordering is based on the ordering of the elements specified byc
.MapBinaryHeap
(Comparator<T> comp) Creates aMapBinaryHeap
whose heap ordering is based on the ordering of the elements specified bycomp
. -
Method Summary
Modifier and TypeMethodDescriptionboolean
Insertso
into this collection.void
clear()
boolean
element()
private void
initialize
(Comparator<T> comp) boolean
isEmpty()
Returnstrue
if this collection contains no elements, andfalse
otherwise.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
private int
parent
(int i) Returns the index of the parent of the element at indexi
of the heap.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.poll()
private int
rChild
(int i) Returns the index of the right child of the element at indexi
of the heap.remove()
boolean
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()
private void
swap
(int i, int j) Swaps the positions of the elements at indicesi
andj
of the heap.void
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
Methods inherited from interface java.util.Collection
addAll, containsAll, equals, hashCode, parallelStream, removeIf, spliterator, stream, toArray, toArray, toArray
-
Field Details
-
heap
-
object_indices
-
comp
-
TOP
private static final int TOP- See Also:
-
-
Constructor Details
-
MapBinaryHeap
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
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
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 Details
-
initialize
-
clear
public void clear()- Specified by:
clear
in interfaceCollection<T>
- Overrides:
clear
in classAbstractCollection<T>
- See Also:
-
add
Insertso
into this collection.- Specified by:
add
in interfaceCollection<T>
- Specified by:
add
in interfaceQueue<T>
- Overrides:
add
in classAbstractCollection<T>
-
isEmpty
public boolean isEmpty()Returnstrue
if this collection contains no elements, andfalse
otherwise.- Specified by:
isEmpty
in interfaceCollection<T>
- Overrides:
isEmpty
in classAbstractCollection<T>
-
peek
Returns the element at the top of the heap; does not alter the heap. -
size
public int size()- Specified by:
size
in interfaceCollection<T>
- Specified by:
size
in classAbstractCollection<T>
- Returns:
- the size of this heap
-
update
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
- Specified by:
contains
in interfaceCollection<T>
- Overrides:
contains
in classAbstractCollection<T>
-
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
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
Returns anIterator
that does not support modification of the heap.- Specified by:
iterator
in interfaceCollection<T>
- Specified by:
iterator
in interfaceIterable<T>
- Specified by:
iterator
in classAbstractCollection<T>
-
remove
This data structure does not support the removal of arbitrary elements.- Specified by:
remove
in interfaceCollection<T>
- Overrides:
remove
in classAbstractCollection<T>
-
removeAll
This data structure does not support the removal of arbitrary elements.- Specified by:
removeAll
in interfaceCollection<T>
- Overrides:
removeAll
in classAbstractCollection<T>
-
retainAll
This data structure does not support the removal of arbitrary elements.- Specified by:
retainAll
in interfaceCollection<T>
- Overrides:
retainAll
in classAbstractCollection<T>
-
element
- Specified by:
element
in interfaceQueue<T>
- Throws:
NoSuchElementException
-
offer
-
poll
-
remove
-