E
- element class.public class BinaryHeap<E> extends AbstractSmartCollection<E> implements SmartDynamicPriorityQueue<E>, CapacityManagement
PriorityQueue
implementation using a binary heap.Modifier | Constructor and Description |
---|---|
protected |
BinaryHeap(int initCapacity,
Collection<? extends E> initValues,
Comparator<? super E> comparator) |
protected |
BinaryHeap(int initialCapacity,
Comparator<? super E> comparator) |
Modifier and Type | Method and Description |
---|---|
static <E extends Comparable<E>> |
create() |
static <E extends Comparable<E>> |
create(Collection<? extends E> initValues) |
static <E extends Comparable<E>> |
create(int initialCapacity) |
static <E extends Comparable<E>> |
create(int initialCapacity,
Collection<? extends E> initValues) |
static <E> BinaryHeap<E> |
createCmp(Comparator<? super E> comparator) |
static <E> BinaryHeap<E> |
createCmp(Comparator<? super E> comparator,
Collection<? extends E> initValues) |
static <E> BinaryHeap<E> |
createCmp(Comparator<? super E> comparator,
int initialCapacity) |
static <E> BinaryHeap<E> |
createCmp(Comparator<? super E> comparator,
int initialCapacity,
Collection<? extends E> initValues) |
void |
deepClear()
Thoroughly clears the collection, fixing all issues that may have been
caused by a call of the above
SmartCollection.quickClear() . |
boolean |
ensureAdditionalCapacity(int additionalCapacity)
Ensures that the internal storage has room for at least
the provided number of additional elements.
|
boolean |
ensureCapacity(int minCapacity)
Ensures that the internal storage has room for at least
the provided number of elements.
|
E |
extractMin()
Retrieves and remove the element with the minimum key in the priority
queue.
|
E |
get(ElementReference ref)
Retrieves an element by its reference.
|
void |
hintNextCapacity(int nextCapacityHint)
Gives a hint regarding the capacity that should be reserved when
resizing the internal storage for the next time.
|
void |
keyChanged(ElementReference ref)
Notifies the implementation that the key of an element has changed.
|
void |
keyChanged(int index) |
E |
peekMin()
Retrieves, but does not remove the element with the minimum key
in the priority queue.
|
void |
quickClear()
Quickly clears this collection.
|
net.automatalib.commons.smartcollections.BinaryHeap.Reference<E> |
referencedAdd(E elem)
Adds an element to the collection, returning a reference to the
newly added element.
|
Iterator<ElementReference> |
referenceIterator()
Retrieves an iterator for iterating over the references of elements
in this collection.
|
void |
remove(ElementReference ref)
Removes an element (by its reference) from the collection.
|
void |
replace(ElementReference ref,
E newElement)
Replaces the element referenced by the given reference with
the specified element.
|
int |
size() |
add, addAll, addAll, choose, chooseRef, find, iterator, references, remove
addAll, clear, contains, containsAll, isEmpty, removeAll, retainAll, toArray, toArray, toString
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
addAll, addAll, choose, chooseRef, find, references, remove
add, addAll, clear, contains, containsAll, equals, hashCode, isEmpty, iterator, parallelStream, removeAll, removeIf, retainAll, spliterator, stream, toArray, toArray
protected BinaryHeap(int initialCapacity, Comparator<? super E> comparator)
protected BinaryHeap(int initCapacity, Collection<? extends E> initValues, Comparator<? super E> comparator)
public static <E extends Comparable<E>> BinaryHeap<E> create()
public static <E extends Comparable<E>> BinaryHeap<E> create(int initialCapacity)
public static <E extends Comparable<E>> BinaryHeap<E> create(Collection<? extends E> initValues)
public static <E extends Comparable<E>> BinaryHeap<E> create(int initialCapacity, Collection<? extends E> initValues)
public static <E> BinaryHeap<E> createCmp(Comparator<? super E> comparator)
public static <E> BinaryHeap<E> createCmp(Comparator<? super E> comparator, int initialCapacity)
public static <E> BinaryHeap<E> createCmp(Comparator<? super E> comparator, Collection<? extends E> initValues)
public static <E> BinaryHeap<E> createCmp(Comparator<? super E> comparator, int initialCapacity, Collection<? extends E> initValues)
public E extractMin()
SmartPriorityQueue
extractMin
in interface SmartPriorityQueue<E>
public void keyChanged(int index)
public E peekMin()
SmartPriorityQueue
peekMin
in interface SmartPriorityQueue<E>
public net.automatalib.commons.smartcollections.BinaryHeap.Reference<E> referencedAdd(E elem)
SmartCollection
referencedAdd
in interface SmartCollection<E>
elem
- the element to be added.public int size()
size
in interface Collection<E>
size
in class AbstractCollection<E>
public void keyChanged(ElementReference ref)
SmartDynamicPriorityQueue
keyChanged
in interface SmartDynamicPriorityQueue<E>
ref
- the reference for the element whose key has changed.public E get(ElementReference ref)
SmartCollection
get
in interface SmartCollection<E>
ref
- the element's reference.public Iterator<ElementReference> referenceIterator()
SmartCollection
referenceIterator
in interface SmartCollection<E>
public void remove(ElementReference ref)
SmartCollection
remove
in interface SmartCollection<E>
ref
- the reference to the element to be removed.public void replace(ElementReference ref, E newElement)
SmartCollection
replace
in interface SmartCollection<E>
ref
- the reference of the element to be replaced.newElement
- the replacement.public boolean ensureCapacity(int minCapacity)
CapacityManagement
ensureCapacity
in interface CapacityManagement
minCapacity
- the minimal number of elements the storage should
have room for.true
iff the internal storage had to be resized,
false
otherwise.public boolean ensureAdditionalCapacity(int additionalCapacity)
CapacityManagement
CapacityManagement.ensureCapacity(int)
with an argument of
size() + additionalCapacity
.ensureAdditionalCapacity
in interface CapacityManagement
additionalCapacity
- the number of additional elements the storage
should have room for.true
iff the internal storage had to be resized,
false
otherwise.public void hintNextCapacity(int nextCapacityHint)
CapacityManagement
CapacityManagement.ensureCapacity(int)
, i.e. it reserves the
specified capacity at the time the next resizing of the internal
storage is performed.
This method is useful when a not too imprecise upper bound on the
elements that will in consequence be added is known. Since the actual
number of elements added may be lower than the specified upper bound,
a resizing that would have been performed by
CapacityManagement.ensureCapacity(int)
might not be necessary.hintNextCapacity
in interface CapacityManagement
nextCapacityHint
- the next capacity hint.public void deepClear()
SmartCollection
SmartCollection.quickClear()
.deepClear
in interface SmartCollection<E>
deepClear
in class AbstractSmartCollection<E>
public void quickClear()
SmartCollection
Collection.clear()
. However, this could also have side-effects
like hampering the garbage collection or such.
After calling this method, even a call of the normal
Collection.clear()
is not guaranteed to fix all these issues.
This can only be achieved by the method SmartCollection.deepClear()
below.quickClear
in interface SmartCollection<E>
quickClear
in class AbstractSmartCollection<E>
Copyright © 2015. All Rights Reserved.