- Type Parameters:
E
- The type of object contained in the BinaryHeapDouble.
- All Implemented Interfaces:
Iterable<PriorityQueueNode.Double<E>>
,Collection<PriorityQueueNode.Double<E>>
,Queue<PriorityQueueNode.Double<E>>
,MergeablePriorityQueueDouble<E,
,BinaryHeapDouble<E>> PriorityQueueDouble<E>
,Copyable<BinaryHeapDouble<E>>
An implementation of a Binary Heap. An instance of a BinaryHeapDouble contains (element, priority) pairs, such that the elements are distinct. The priority values are of type double.
Priority order:
BinaryHeapDouble instances are created via factory methods with names beginning
with create
. The priority order depends upon the factory method
used to create the BinaryHeapDouble. Methods named createMinHeap
produce
a min heap with priority order minimum-priority-first-out. Methods named
createMaxHeap
produce a max heap with priority order
maximum-priority-first-out.
Distinctness:
The Object.hashCode()
and Object.equals(java.lang.Object)
methods are used
to enforce distinctness, so be sure that the class of the elements
properly implements these methods, or else behavior is not guaranteed.
Creating instances: To create an instance, use one of the factory methods, such as with:
BinaryHeapDouble<String> pq = BinaryHeapDouble.createMinHeap();
Method runtimes: The asymptotic runtime of the methods of this class are as follows (where n is the current size of the heap and m is the size of a Collection parameter where relevant):
- O(1):
contains(java.lang.Object)
,createMaxHeap()
,createMaxHeap(int)
,createMinHeap()
,createMinHeap(int)
,PriorityQueueDouble.element()
,isEmpty()
,iterator()
,peek()
,peekElement()
,peekPriority()
,peekPriority(Object)
,size()
- O(lg n):
PriorityQueueDouble.add(Object, double)
,PriorityQueueDouble.add(PriorityQueueNode.Double)
,change(E, double)
,demote(E, double)
,offer(Object, double)
,offer(PriorityQueueNode.Double)
,poll()
,pollElement()
,promote(E, double)
,PriorityQueueDouble.remove()
,remove(Object)
,PriorityQueueDouble.removeElement()
- O(m):
PriorityQueueDouble.containsAll(Collection)
,createMaxHeap(Collection)
,createMinHeap(Collection)
- O(n):
clear()
,copy()
,ensureCapacity(int)
,equals(java.lang.Object)
,hashCode()
,toArray()
,toArray(Object[])
,trimToSize()
- O(n + m):
addAll(Collection)
,merge(BinaryHeapDouble)
,removeAll(Collection)
,retainAll(Collection)
-
Field Summary
FieldsModifier and TypeFieldDescriptionstatic final int
The default initial capacity. -
Method Summary
Modifier and TypeMethodDescriptionfinal boolean
addAll
(Collection<? extends PriorityQueueNode.Double<E>> c) Adds all (element, priority) pairs from a Collection to the PriorityQueueDouble, provided the elements are not already in the PriorityQueueDouble.final boolean
Changes the priority of an element if the element is present in the PriorityQueueDouble, and otherwise adds the (element, priority) pair to the PriorityQueueDouble.final void
clear()
Clears the PriorityQueueDouble, removing all elements.final boolean
Checks if this PriorityQueueDouble contains a given element or an (element, priority) pair with a given element.copy()
Creates an identical copy of this object.static <E> BinaryHeapDouble<E>
Creates an empty BinaryHeapDouble with theDEFAULT_INITIAL_CAPACITY
as the initial capacity, and a maximum-priority-first-out priority order.static <E> BinaryHeapDouble<E>
createMaxHeap
(int initialCapacity) Creates an empty BinaryHeapDouble with a specified initial capacity, and a maximum-priority-first-out priority order.static <E> BinaryHeapDouble<E>
createMaxHeap
(Collection<PriorityQueueNode.Double<E>> initialElements) Creates a BinaryHeapDouble from a collection of (element, priority) pairs, with a maximum-priority-first-out priority order.static <E> BinaryHeapDouble<E>
Creates an empty BinaryHeapDouble with theDEFAULT_INITIAL_CAPACITY
as the initial capacity, and a minimum-priority-first-out priority order.static <E> BinaryHeapDouble<E>
createMinHeap
(int initialCapacity) Creates an empty BinaryHeapDouble with a specified initial capacity, and a minimum-priority-first-out priority order.static <E> BinaryHeapDouble<E>
createMinHeap
(Collection<PriorityQueueNode.Double<E>> initialElements) Creates a BinaryHeapDouble from a collection of (element, priority) pairs, with a minimum-priority-first-out priority order.final boolean
Demotes an element relative to priority order if the element is present in the PriorityQueueDouble.final void
ensureCapacity
(int minCapacity) Increases the capacity if the capacity is not already at least the specified minimum.boolean
Checks if this BinaryHeapDouble contains the same (element, priority) pairs as another BinaryHeapDouble, including the specific order within the BinaryHeapDouble, as well as that the priority order is the same.int
hashCode()
Computes a hashCode for the BinaryHeapDouble.final boolean
isEmpty()
Checks if the PriorityQueueDouble is empty.final Iterator<PriorityQueueNode.Double<E>>
iterator()
Returns an iterator over the (element, priority) pairs in a mostly arbitrary order (i.e., you must not assume any particular order).boolean
merge
(BinaryHeapDouble<E> other) Merges another priority queue into this one, adding all of its (element, priority) pairs.final boolean
Adds an (element, priority) pair to the PriorityQueueDouble with a specified priority, provided the element is not already in the PriorityQueueDouble.final boolean
offer
(PriorityQueueNode.Double<E> pair) Adds an (element, priority) pair to the PriorityQueueDouble, provided the element is not already in the PriorityQueueDouble.final PriorityQueueNode.Double<E>
peek()
Gets the next (element, priority) pair in priority order from this PriorityQueueDouble, without removing it.final E
Gets the next element in priority order from this PriorityQueueDouble, without removing it.final double
Gets the priority of the next element in priority order in the PriorityQueueDouble.final double
peekPriority
(E element) Gets the priority of a specified element if it is present in the PriorityQueueDouble.final PriorityQueueNode.Double<E>
poll()
Removes and returns the next (element, priority) pair in priority order from this PriorityQueueDouble.final E
Removes and returns the next element in priority order from this PriorityQueueDouble.final boolean
Promotes an element relative to priority order if the element is present in the PriorityQueueDouble.final boolean
Removes from this PriorityQueueDouble the (element, priority) pair, if present, for a specified element or element from a specified (element, priority) pair.final boolean
removeAll
(Collection<?> c) Removes from this PriorityQueueDouble all (element, priority) pairs such that a given Collection c either contains the element or contains an (element, priority) pair with the same element.final boolean
retainAll
(Collection<?> c) Removes from this PriorityQueueDouble all (element, priority) pairs except for the elements or (element, priority) pairs contained in a given Collection c.final int
size()
Gets the current size of the PriorityQueueDouble, which is the number of (element, value) pairs that it contains.final Object[]
toArray()
Returns an array containing all of the (element, priority) pairs contained in the PriorityQueueDouble.final <T> T[]
toArray
(T[] array) Returns an array containing all of the (element, priority) pairs contained in the PriorityQueueDouble.final void
Decreases the capacity to the current size of the BinaryHeapDouble, provided size is at least 1, and otherwise decreases capacity to 1.Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, toString, wait, wait, wait
Methods inherited from interface java.util.Collection
parallelStream, removeIf, spliterator, stream, toArray
Methods inherited from interface org.cicirello.ds.PriorityQueueDouble
add, add, containsAll, element, remove, removeElement
-
Field Details
-
DEFAULT_INITIAL_CAPACITY
public static final int DEFAULT_INITIAL_CAPACITYThe default initial capacity.- See Also:
-
-
Method Details
-
copy
Description copied from interface:Copyable
Creates an identical copy of this object. -
createMinHeap
Creates an empty BinaryHeapDouble with theDEFAULT_INITIAL_CAPACITY
as the initial capacity, and a minimum-priority-first-out priority order.- Type Parameters:
E
- The type of elements contained in the BinaryHeapDouble.- Returns:
- an empty BinaryHeapDouble with a minimum-priority-first-out priority order
-
createMinHeap
Creates an empty BinaryHeapDouble with a specified initial capacity, and a minimum-priority-first-out priority order.- Type Parameters:
E
- The type of elements contained in the BinaryHeapDouble.- Parameters:
initialCapacity
- The initial capacity, which must be positive.- Returns:
- an empty BinaryHeapDouble with a minimum-priority-first-out priority order
- Throws:
IllegalArgumentException
- if initialCapacity is less than or equal to 0.
-
createMinHeap
public static <E> BinaryHeapDouble<E> createMinHeap(Collection<PriorityQueueNode.Double<E>> initialElements) Creates a BinaryHeapDouble from a collection of (element, priority) pairs, with a minimum-priority-first-out priority order.- Type Parameters:
E
- The type of elements contained in the BinaryHeapDouble.- Parameters:
initialElements
- The initial collection of (element, priority) pairs, which must be non-empty.- Returns:
- a BinaryHeapDouble with a minimum-priority-first-out priority order
- Throws:
IllegalArgumentException
- if initialElements is empty, or if more than one pair in initialElements contains the same element.
-
createMaxHeap
Creates an empty BinaryHeapDouble with theDEFAULT_INITIAL_CAPACITY
as the initial capacity, and a maximum-priority-first-out priority order.- Type Parameters:
E
- The type of elements contained in the BinaryHeapDouble.- Returns:
- an empty BinaryHeapDouble with a maximum-priority-first-out priority order
-
createMaxHeap
Creates an empty BinaryHeapDouble with a specified initial capacity, and a maximum-priority-first-out priority order.- Type Parameters:
E
- The type of elements contained in the BinaryHeapDouble.- Parameters:
initialCapacity
- The initial capacity, which must be positive.- Returns:
- an empty BinaryHeapDouble with a maximum-priority-first-out priority order
- Throws:
IllegalArgumentException
- if initialCapacity is less than or equal to 0.
-
createMaxHeap
public static <E> BinaryHeapDouble<E> createMaxHeap(Collection<PriorityQueueNode.Double<E>> initialElements) Creates a BinaryHeapDouble from a collection of (element, priority) pairs, with a maximum-priority-first-out priority order.- Type Parameters:
E
- The type of elements contained in the BinaryHeapDouble.- Parameters:
initialElements
- The initial collection of (element, priority) pairs, which must be non-empty.- Returns:
- a BinaryHeapDouble with a maximum-priority-first-out priority order
- Throws:
IllegalArgumentException
- if initialElements is empty, or if more than one pair in initialElements contains the same element.
-
addAll
Adds all (element, priority) pairs from a Collection to the PriorityQueueDouble, provided the elements are not already in the PriorityQueueDouble. The default implementation calls thePriorityQueueDouble.add(PriorityQueueNode.Double)
for each pair in the Collection.The runtime of this method is O(n + m) where n is current size of the heap and m is the size of the Collection c. In general this is more efficient than calling add repeatedly, unless you are adding a relatively small number of elements, in which case you should instead call either
offer(PriorityQueueNode.Double)
orPriorityQueueDouble.add(PriorityQueueNode.Double)
for each (element, priority) pair you want to add.- Specified by:
addAll
in interfaceCollection<E>
- Specified by:
addAll
in interfacePriorityQueueDouble<E>
- Parameters:
c
- the Collection of (element, priority) pairs to add.- Returns:
- true if the (element, priority) pairs were added.
- Throws:
IllegalArgumentException
- if the heap already contains any of the (element, priority) pairs.
-
change
Description copied from interface:PriorityQueueDouble
Changes the priority of an element if the element is present in the PriorityQueueDouble, and otherwise adds the (element, priority) pair to the PriorityQueueDouble.- Specified by:
change
in interfacePriorityQueueDouble<E>
- Parameters:
element
- The element whose priority is to change.priority
- Its new priority.- Returns:
- true if and only if the PriorityQueueDouble changed as a consequence of this method call.
-
clear
public final void clear()Description copied from interface:PriorityQueueDouble
Clears the PriorityQueueDouble, removing all elements.- Specified by:
clear
in interfaceCollection<E>
- Specified by:
clear
in interfacePriorityQueueDouble<E>
-
contains
Description copied from interface:PriorityQueueDouble
Checks if this PriorityQueueDouble contains a given element or an (element, priority) pair with a given element.- Specified by:
contains
in interfaceCollection<E>
- Specified by:
contains
in interfacePriorityQueueDouble<E>
- Parameters:
o
- An element or (element, priority) pair to check for containment of the element.- Returns:
- true if and only if this PriorityQueueDouble contains the element.
-
demote
Description copied from interface:PriorityQueueDouble
Demotes an element relative to priority order if the element is present in the PriorityQueueDouble. For a min-heap, demotion means increasing the element's priority, while for a max-heap, demotion means decreasing its priority. If the element is not in the PriorityQueueDouble, or if its new priority is not a demotion, then this method does nothing.- Specified by:
demote
in interfacePriorityQueueDouble<E>
- Parameters:
element
- The element whose priority is to change.priority
- Its new priority.- Returns:
- true if and only if the PriorityQueueDouble changed as a consequence of this method call.
-
ensureCapacity
public final void ensureCapacity(int minCapacity) Increases the capacity if the capacity is not already at least the specified minimum. If the capacity is at or above the requested minimum, then this method does nothing.- Parameters:
minCapacity
- The desired minimum capacity.
-
equals
Checks if this BinaryHeapDouble contains the same (element, priority) pairs as another BinaryHeapDouble, including the specific order within the BinaryHeapDouble, as well as that the priority order is the same.- Specified by:
equals
in interfaceCollection<E>
- Overrides:
equals
in classObject
- Parameters:
other
- The other BinaryHeapDouble.- Returns:
- true if and only if this and other contain the same (element, priority) pairs, with the same priority order.
-
hashCode
public int hashCode()Computes a hashCode for the BinaryHeapDouble.- Specified by:
hashCode
in interfaceCollection<E>
- Overrides:
hashCode
in classObject
- Returns:
- a hashCode
-
isEmpty
public final boolean isEmpty()Description copied from interface:PriorityQueueDouble
Checks if the PriorityQueueDouble is empty.- Specified by:
isEmpty
in interfaceCollection<E>
- Specified by:
isEmpty
in interfacePriorityQueueDouble<E>
- Returns:
- true if and only if it is empty
-
iterator
Description copied from interface:PriorityQueueDouble
Returns an iterator over the (element, priority) pairs in a mostly arbitrary order (i.e., you must not assume any particular order).- Specified by:
iterator
in interfaceCollection<E>
- Specified by:
iterator
in interfaceIterable<E>
- Specified by:
iterator
in interfacePriorityQueueDouble<E>
- Returns:
- an iterator over the (element, priority) pairs
-
merge
Merges another priority queue into this one, adding all of its (element, priority) pairs. This is a destructive operation with no guarantees to the state of the other priority queue upon completion. Additionally, implementations of this method may assume that
other
andthis
do not share any elements, and the priority queue may become unstable if they do. The priority order of both priority queues must be the same (e.g., both minheaps or both maxheaps).- Specified by:
merge
in interfaceMergeablePriorityQueueDouble<E,
BinaryHeapDouble<E>> - Parameters:
other
- The priority queue that you want to merge intothis
. Implementations need not make any guarantees as to the state ofother
upon completion.- Returns:
- true if and only if this priority queue changed as a result of the merge
- Throws:
IllegalArgumentException
- if this and other have different priority-order (e.g., one is a minheap while the other is a maxheap)
-
offer
Description copied from interface:PriorityQueueDouble
Adds an (element, priority) pair to the PriorityQueueDouble with a specified priority, provided the element is not already in the PriorityQueueDouble.- Specified by:
offer
in interfacePriorityQueueDouble<E>
- Parameters:
element
- The element.priority
- The priority of the element.- Returns:
- true if the (element, priority) pair was added, and false if the PriorityQueueDouble already contained the element.
-
offer
Description copied from interface:PriorityQueueDouble
Adds an (element, priority) pair to the PriorityQueueDouble, provided the element is not already in the PriorityQueueDouble. -
peekElement
Description copied from interface:PriorityQueueDouble
Gets the next element in priority order from this PriorityQueueDouble, without removing it.- Specified by:
peekElement
in interfacePriorityQueueDouble<E>
- Returns:
- the next element in priority order, or null if empty.
-
peek
Description copied from interface:PriorityQueueDouble
Gets the next (element, priority) pair in priority order from this PriorityQueueDouble, without removing it. -
peekPriority
public final double peekPriority()Description copied from interface:PriorityQueueDouble
Gets the priority of the next element in priority order in the PriorityQueueDouble.- Specified by:
peekPriority
in interfacePriorityQueueDouble<E>
- Returns:
- the priority of the next element in priority order.
-
peekPriority
Description copied from interface:PriorityQueueDouble
Gets the priority of a specified element if it is present in the PriorityQueueDouble. This interface does not define the behavior when the element is not present. Implementations may define the behavior when the element is not present.- Specified by:
peekPriority
in interfacePriorityQueueDouble<E>
- Parameters:
element
- The element whose priority is returned.- Returns:
- the priority of a specified element.
-
pollElement
Description copied from interface:PriorityQueueDouble
Removes and returns the next element in priority order from this PriorityQueueDouble.- Specified by:
pollElement
in interfacePriorityQueueDouble<E>
- Returns:
- the next element in priority order, or null if empty.
-
poll
Description copied from interface:PriorityQueueDouble
Removes and returns the next (element, priority) pair in priority order from this PriorityQueueDouble. -
promote
Description copied from interface:PriorityQueueDouble
Promotes an element relative to priority order if the element is present in the PriorityQueueDouble. For a min-heap, promotion means decreasing the element's priority, while for a max-heap, promotion means increasing its priority. If the element is not in the PriorityQueueDouble, or if its new priority is not a promotion, then this method does nothing.- Specified by:
promote
in interfacePriorityQueueDouble<E>
- Parameters:
element
- The element whose priority is to change.priority
- Its new priority.- Returns:
- true if and only if the PriorityQueueDouble changed as a consequence of this method call.
-
remove
Description copied from interface:PriorityQueueDouble
Removes from this PriorityQueueDouble the (element, priority) pair, if present, for a specified element or element from a specified (element, priority) pair.- Specified by:
remove
in interfaceCollection<E>
- Specified by:
remove
in interfacePriorityQueueDouble<E>
- Parameters:
o
- An element or (element, priority) pair, such that element designates the desired pair to remove (note that if you pass an (element, priority) pair, only the element must match to cause removal.- Returns:
- true if and only if an (element, priority) pair was removed as a result of this method call.
-
removeAll
Removes from this PriorityQueueDouble all (element, priority) pairs such that a given Collection c either contains the element or contains an (element, priority) pair with the same element.The runtime of this method is O(n + m) where n is current size of the heap and m is the size of the Collection c. In general this is more efficient than calling remove repeatedly, unless you are removing a relatively small number of elements, in which case you should instead call
remove(Object)
for each element you want to remove.- Specified by:
removeAll
in interfaceCollection<E>
- Specified by:
removeAll
in interfacePriorityQueueDouble<E>
- Parameters:
c
- A Collection of elements or (element, priority) pairs for removal.- Returns:
- true if and only if this PriorityQueueDouble changed as a result of this method.
-
retainAll
Removes from this PriorityQueueDouble all (element, priority) pairs except for the elements or (element, priority) pairs contained in a given Collection c.The runtime of this method is O(n + m) where n is current size of the heap and m is the size of the Collection c. In general this is more efficient than calling remove repeatedly, unless you are removing a relatively small number of elements, in which case you should instead call
remove(Object)
for each element you want to remove.- Specified by:
retainAll
in interfaceCollection<E>
- Specified by:
retainAll
in interfacePriorityQueueDouble<E>
- Parameters:
c
- A Collection of elements or (element, priority) pairs to keep.- Returns:
- true if and only if this PriorityQueueDouble changed as a result of this method.
-
size
public final int size()Description copied from interface:PriorityQueueDouble
Gets the current size of the PriorityQueueDouble, which is the number of (element, value) pairs that it contains.- Specified by:
size
in interfaceCollection<E>
- Specified by:
size
in interfacePriorityQueueDouble<E>
- Returns:
- the current size of the PriorityQueueDouble.
-
toArray
Description copied from interface:PriorityQueueDouble
Returns an array containing all of the (element, priority) pairs contained in the PriorityQueueDouble. The order is not guaranteed. The runtime component type is Object. The PriorityQueueDouble does not maintain any references to the array that is returned, instead creating a new array upon each call to the toArray method. The length of the array that is returned is equal to the currentPriorityQueueDouble.size()
of the PriorityQueueDouble.- Specified by:
toArray
in interfaceCollection<E>
- Specified by:
toArray
in interfacePriorityQueueDouble<E>
- Returns:
- an array, whose runtime component type is Object, containing all of the (element, priority) pairs currently in the PriorityQueueDouble.
-
toArray
public final <T> T[] toArray(T[] array) Description copied from interface:PriorityQueueDouble
Returns an array containing all of the (element, priority) pairs contained in the PriorityQueueDouble. The order is not guaranteed. The runtime component type is the same as the array passed to it as a parameter. If the specified array is large enough, then it is used, otherwise a new array is allocated whose length is equal to the currentPriorityQueueDouble.size()
of the PriorityQueueDouble. If the specified array is larger than the current size() of the PriorityQueueDouble, the first extra cell is set to null.- Specified by:
toArray
in interfaceCollection<E>
- Specified by:
toArray
in interfacePriorityQueueDouble<E>
- Type Parameters:
T
- The component type of the array to contain the (element, priority) pairs- Parameters:
array
- The array in which to place the (element, priority) pairs, if it is sufficiently large, otherwise a new array of lengthPriorityQueueDouble.size()
is allocated of the same runtime type as array.- Returns:
- The array in which the (element, priority) pairs have been inserted.
-
trimToSize
public final void trimToSize()Decreases the capacity to the current size of the BinaryHeapDouble, provided size is at least 1, and otherwise decreases capacity to 1. If the size and the capacity are the same, then this method does nothing.
-