E - element class.public class BinaryHeap<E> extends AbstractSmartCollection<E> implements SmartDynamicPriorityQueue<E>, CapacityManagement, Queue<E>
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(). |
E |
element() |
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 removes 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) |
boolean |
offer(E e) |
E |
peek() |
E |
peekMin()
Retrieves, but does not remove the element with the minimum key in the priority queue.
|
E |
poll() |
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.
|
E |
remove() |
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, removeaddAll, clear, contains, containsAll, isEmpty, removeAll, retainAll, toArray, toArray, toStringclone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, waitaddAll, addAll, choose, chooseRef, find, references, removeadd, addAll, clear, contains, containsAll, equals, hashCode, isEmpty, iterator, parallelStream, removeAll, removeIf, retainAll, spliterator, stream, toArray, toArrayprotected BinaryHeap(int initCapacity,
Collection<? extends E> initValues,
Comparator<? super E> comparator)
protected BinaryHeap(int initialCapacity,
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 int size()
size in interface Collection<E>size in class AbstractCollection<E>public E get(ElementReference ref)
SmartCollectionIf the reference belongs to another collection, the behavior is undefined.
get in interface SmartCollection<E>ref - the element's reference.public net.automatalib.commons.smartcollections.BinaryHeap.Reference<E> referencedAdd(E elem)
SmartCollectionreferencedAdd in interface SmartCollection<E>elem - the element to be added.public void remove(ElementReference ref)
SmartCollectionIf the reference does not belong to this collection, the behavior is undefined.
remove in interface SmartCollection<E>ref - the reference to the element to be removed.public Iterator<ElementReference> referenceIterator()
SmartCollectionreferenceIterator in interface SmartCollection<E>public void replace(ElementReference ref, E newElement)
SmartCollectionreplace in interface SmartCollection<E>ref - the reference of the element to be replaced.newElement - the replacement.public void keyChanged(ElementReference ref)
SmartDynamicPriorityQueuekeyChanged in interface SmartDynamicPriorityQueue<E>ref - the reference for the element whose key has changed.public void keyChanged(int index)
public boolean ensureCapacity(int minCapacity)
CapacityManagementensureCapacity in interface CapacityManagementminCapacity - 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
Calling this method is equivalent to calling the above CapacityManagement.ensureCapacity(int) with an argument of
size() + additionalCapacity.
ensureAdditionalCapacity in interface CapacityManagementadditionalCapacity - 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)
CapacityManagementCapacityManagement.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 CapacityManagementnextCapacityHint - the next capacity hint.public void quickClear()
SmartCollection
Depending on the implementation, this may be just the same as 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>public void deepClear()
SmartCollectionSmartCollection.quickClear().deepClear in interface SmartCollection<E>deepClear in class AbstractSmartCollection<E>public E peekMin()
SmartPriorityQueuepeekMin in interface SmartPriorityQueue<E>public E extractMin()
SmartPriorityQueueextractMin in interface SmartPriorityQueue<E>Copyright © 2020. All rights reserved.