T
- type of the contained elements.public class HeapPriorityQueue<T extends HeapPriorityQueueElement> extends AbstractHeapPriorityQueue<T>
HeapPriorityQueueElement
objects. This heap supports
fast deletes because it manages position indexes of the contained HeapPriorityQueueElement
s. The heap implementation is a simple binary tree stored inside an
array. Element indexes in the heap array start at 1 instead of 0 to make array index computations
a bit simpler in the hot methods. Object identification of remove is based on object identity and
not on equals. We use the managed index from HeapPriorityQueueElement
to find an element
in the queue array to support fast deletes.
Possible future improvements:
Modifier and Type | Field and Description |
---|---|
protected PriorityComparator<T> |
elementPriorityComparator
Comparator for the priority of contained elements.
|
queue, size
Constructor and Description |
---|
HeapPriorityQueue(PriorityComparator<T> elementPriorityComparator,
int minimumCapacity)
Creates an empty
HeapPriorityQueue with the requested initial capacity. |
Modifier and Type | Method and Description |
---|---|
protected void |
addInternal(T element)
Implements how to add an element to the queue.
|
void |
adjustModifiedElement(T element) |
protected int |
getHeadElementIndex()
Returns the start index of the queue elements in the array.
|
protected T |
removeInternal(int removeIdx)
Implements how to remove the element at the given index from the queue.
|
add, addAll, clear, isEmpty, iterator, moveElementToIdx, peek, poll, remove, resizeForBulkLoad, resizeQueueArray, size, toArray
@Nonnull protected final PriorityComparator<T extends HeapPriorityQueueElement> elementPriorityComparator
public HeapPriorityQueue(@Nonnull PriorityComparator<T> elementPriorityComparator, @Nonnegative int minimumCapacity)
HeapPriorityQueue
with the requested initial capacity.elementPriorityComparator
- comparator for the priority of contained elements.minimumCapacity
- the minimum and initial capacity of this priority queue.protected int getHeadElementIndex()
AbstractHeapPriorityQueue
getHeadElementIndex
in class AbstractHeapPriorityQueue<T extends HeapPriorityQueueElement>
protected void addInternal(@Nonnull T element)
AbstractHeapPriorityQueue
addInternal
in class AbstractHeapPriorityQueue<T extends HeapPriorityQueueElement>
element
- the element to add.protected T removeInternal(int removeIdx)
AbstractHeapPriorityQueue
removeInternal
in class AbstractHeapPriorityQueue<T extends HeapPriorityQueueElement>
removeIdx
- the index to remove.Copyright © 2014–2021 The Apache Software Foundation. All rights reserved.