Package org.jheaps.array
Class AbstractArrayWeakHeap<K>
java.lang.Object
org.jheaps.array.AbstractArrayWeakHeap<K>
- Type Parameters:
K
- the type of keys maintained by this heap
- All Implemented Interfaces:
Serializable
,Heap<K>
- Direct Known Subclasses:
AbstractArrayHeap
,BinaryArrayWeakHeap
An abstract weak heap with an array representation.
-
Field Summary
FieldsModifier and TypeFieldDescriptionprotected K[]
The array used for representing the heap.protected final Comparator
<? super K> The comparator used to maintain order in this heap, or null if it uses the natural ordering of its keys.protected static final int
Limit for the heap capacity when down-sizing.protected static final int
The maximum heap capacity.protected static final int
The minimum heap capacity.protected final int
Minimum capacity due to initially requested capacity.private static final long
protected int
Number of elements in the heap. -
Constructor Summary
ConstructorsConstructorDescriptionAbstractArrayWeakHeap
(Comparator<? super K> comparator, int capacity) Constructor -
Method Summary
Modifier and TypeMethodDescriptionprotected final void
checkCapacity
(int capacity) Check that a capacity is valid.void
clear()
Clear all the elements of this heap.Comparator
<? super K> Returns the comparator used to order the keys in this heap, ornull
if this heap uses the natural ordering of its keys.protected abstract void
ensureCapacity
(int capacity) Make sure the array representation can hold a certain number of elements.protected abstract void
fixdown
(int k) Downwards fix starting from a particular elementprotected abstract void
fixdownWithComparator
(int k) Downwards fix starting from a particular element.protected abstract void
fixup
(int k) Upwards fix starting from a particular elementprotected abstract void
fixupWithComparator
(int k) Upwards fix starting from a particular element.protected abstract void
initCapacity
(int capacity) Initialize array representation.boolean
isEmpty()
Returnstrue
if this heap is empty.long
size()
Returns the number of elements in this heap.
-
Field Details
-
serialVersionUID
private static final long serialVersionUID- See Also:
-
MAX_HEAP_CAPACITY
protected static final int MAX_HEAP_CAPACITYThe maximum heap capacity.- See Also:
-
MIN_HEAP_CAPACITY
protected static final int MIN_HEAP_CAPACITYThe minimum heap capacity.- See Also:
-
DOWNSIZING_MIN_HEAP_CAPACITY
protected static final int DOWNSIZING_MIN_HEAP_CAPACITYLimit for the heap capacity when down-sizing.- See Also:
-
comparator
The comparator used to maintain order in this heap, or null if it uses the natural ordering of its keys. -
array
The array used for representing the heap. -
size
protected int sizeNumber of elements in the heap. -
minCapacity
protected final int minCapacityMinimum capacity due to initially requested capacity.
-
-
Constructor Details
-
AbstractArrayWeakHeap
Constructor- Parameters:
comparator
- the comparator to usecapacity
- the requested capacity
-
-
Method Details
-
isEmpty
public boolean isEmpty()Returnstrue
if this heap is empty. -
size
public long size()Returns the number of elements in this heap. -
comparator
Returns the comparator used to order the keys in this heap, ornull
if this heap uses the natural ordering of its keys.- Specified by:
comparator
in interfaceHeap<K>
- Returns:
- the comparator used to order the keys in this heap, or
null
if this heap uses the natural ordering of its keys
-
clear
public void clear()Clear all the elements of this heap. -
checkCapacity
protected final void checkCapacity(int capacity) Check that a capacity is valid.- Parameters:
capacity
- the capacity- Throws:
IllegalArgumentException
- if the capacity is negative or more than the maximum array size
-
initCapacity
protected abstract void initCapacity(int capacity) Initialize array representation.- Parameters:
capacity
- the capacity
-
ensureCapacity
protected abstract void ensureCapacity(int capacity) Make sure the array representation can hold a certain number of elements.- Parameters:
capacity
- the capacity
-
fixup
protected abstract void fixup(int k) Upwards fix starting from a particular element- Parameters:
k
- the index of the starting element
-
fixupWithComparator
protected abstract void fixupWithComparator(int k) Upwards fix starting from a particular element. Performs comparisons using the comparator.- Parameters:
k
- the index of the starting element
-
fixdown
protected abstract void fixdown(int k) Downwards fix starting from a particular element- Parameters:
k
- the index of the starting element
-
fixdownWithComparator
protected abstract void fixdownWithComparator(int k) Downwards fix starting from a particular element. Performs comparisons using the comparator.- Parameters:
k
- the index of the starting element
-