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:
java.io.Serializable
,Heap<K>
- Direct Known Subclasses:
AbstractArrayHeap
,BinaryArrayWeakHeap
abstract class AbstractArrayWeakHeap<K> extends java.lang.Object implements Heap<K>, java.io.Serializable
An abstract weak heap with an array representation.
-
-
Field Summary
Fields Modifier and Type Field Description protected K[]
array
The array used for representing the heap.protected java.util.Comparator<? super K>
comparator
The comparator used to maintain order in this heap, or null if it uses the natural ordering of its keys.protected static int
DOWNSIZING_MIN_HEAP_CAPACITY
Limit for the heap capacity when down-sizing.protected static int
MAX_HEAP_CAPACITY
The maximum heap capacity.protected static int
MIN_HEAP_CAPACITY
The minimum heap capacity.protected int
minCapacity
Minimum capacity due to initially requested capacity.private static long
serialVersionUID
protected int
size
Number of elements in the heap.
-
Constructor Summary
Constructors Constructor Description AbstractArrayWeakHeap(java.util.Comparator<? super K> comparator, int capacity)
Constructor
-
Method Summary
All Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description protected void
checkCapacity(int capacity)
Check that a capacity is valid.void
clear()
Clear all the elements of this heap.java.util.Comparator<? super K>
comparator()
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 Detail
-
serialVersionUID
private static final long serialVersionUID
- See Also:
- Constant Field Values
-
MAX_HEAP_CAPACITY
protected static final int MAX_HEAP_CAPACITY
The maximum heap capacity.- See Also:
- Constant Field Values
-
MIN_HEAP_CAPACITY
protected static final int MIN_HEAP_CAPACITY
The minimum heap capacity.- See Also:
- Constant Field Values
-
DOWNSIZING_MIN_HEAP_CAPACITY
protected static final int DOWNSIZING_MIN_HEAP_CAPACITY
Limit for the heap capacity when down-sizing.- See Also:
- Constant Field Values
-
comparator
protected final java.util.Comparator<? super K> comparator
The comparator used to maintain order in this heap, or null if it uses the natural ordering of its keys.
-
array
protected K[] array
The array used for representing the heap.
-
size
protected int size
Number of elements in the heap.
-
minCapacity
protected final int minCapacity
Minimum capacity due to initially requested capacity.
-
-
Constructor Detail
-
AbstractArrayWeakHeap
public AbstractArrayWeakHeap(java.util.Comparator<? super K> comparator, int capacity)
Constructor- Parameters:
comparator
- the comparator to usecapacity
- the requested capacity
-
-
Method Detail
-
isEmpty
public boolean isEmpty()
Returnstrue
if this heap is empty.
-
size
public long size()
Returns the number of elements in this heap.
-
comparator
public java.util.Comparator<? super K> 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:
java.lang.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
-
-