Package org.jheaps.array
Class AbstractArrayAddressableHeap<K,V>
java.lang.Object
org.jheaps.array.AbstractArrayAddressableHeap<K,V>
- Type Parameters:
K
- the type of keys maintained by this heap
- All Implemented Interfaces:
Serializable
,AddressableHeap<K,
V>
- Direct Known Subclasses:
BinaryArrayAddressableHeap
,DaryArrayAddressableHeap
abstract class AbstractArrayAddressableHeap<K,V>
extends Object
implements AddressableHeap<K,V>, Serializable
Abstract implementation of a heap using an array representation.
-
Nested Class Summary
Nested ClassesNested classes/interfaces inherited from interface org.jheaps.AddressableHeap
AddressableHeap.Handle<K,
V> -
Field Summary
FieldsModifier and TypeFieldDescriptionprotected AbstractArrayAddressableHeap<K,
V>.ArrayHandle[] The array use for representing the tree.protected 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.protected static final int
Denotes that a handle is not in the arrayprivate static final long
protected int
Number of elements in the heap. -
Constructor Summary
ConstructorsConstructorDescriptionAbstractArrayAddressableHeap
(Comparator<? super K> comparator, int capacity) -
Method Summary
Modifier and TypeMethodDescriptionprotected final void
checkCapacity
(int capacity) void
clear()
Clear all the elements of the heap.Comparator<? super K>
Returns the comparator used to order the keys in this AddressableHeap, ornull
if this heap uses the natural ordering of its keys.Delete and return an element with the minimum key.protected abstract void
ensureCapacity
(int capacity) findMin()
Find an element with the minimum key.protected abstract void
fixdown
(int k) protected abstract void
fixdownWithComparator
(int k) protected abstract void
fixup
(int k) protected abstract void
fixupWithComparator
(int k) protected abstract void
forceFixup
(int k) Insert a new element into the heap with a null value.Insert a new element into the heap.boolean
isEmpty()
Returnstrue
if this heap is empty.long
size()
Returns the number of elements in the heap.
-
Field Details
-
serialVersionUID
private static final long serialVersionUID- See Also:
-
NO_INDEX
protected static final int NO_INDEXDenotes that a handle is not in the array- 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 use for representing the tree. -
size
protected int sizeNumber of elements in the heap. -
minCapacity
protected final int minCapacityMinimum capacity due to initially requested capacity.
-
-
Constructor Details
-
AbstractArrayAddressableHeap
-
-
Method Details
-
findMin
Find an element with the minimum key.- Specified by:
findMin
in interfaceAddressableHeap<K,
V> - Returns:
- a handle to an element with minimum key
-
isEmpty
public boolean isEmpty()Returnstrue
if this heap is empty.- Specified by:
isEmpty
in interfaceAddressableHeap<K,
V> - Returns:
true
if this heap is empty,false
otherwise
-
size
public long size()Returns the number of elements in the heap.- Specified by:
size
in interfaceAddressableHeap<K,
V> - Returns:
- the number of elements in the heap
-
comparator
Returns the comparator used to order the keys in this AddressableHeap, ornull
if this heap uses the natural ordering of its keys.- Specified by:
comparator
in interfaceAddressableHeap<K,
V> - Returns:
- the comparator used to order the keys in this heap, or
null
if this addressable heap uses the natural ordering of its keys
-
clear
public void clear()Clear all the elements of the heap. After calling this method all handles should be considered invalidated and the behavior of methodsAddressableHeap.Handle.decreaseKey(Object)
andAddressableHeap.Handle.delete()
is undefined.- Specified by:
clear
in interfaceAddressableHeap<K,
V>
-
insert
Insert a new element into the heap with a null value.- Specified by:
insert
in interfaceAddressableHeap<K,
V> - Parameters:
key
- the element's key- Returns:
- a handle for the newly added element
-
insert
Insert a new element into the heap.- Specified by:
insert
in interfaceAddressableHeap<K,
V> - Parameters:
key
- the element's keyvalue
- the element's value- Returns:
- a handle for the newly added element
-
deleteMin
Delete and return an element with the minimum key. If multiple such elements exists, only one of them will be deleted. After the element is deleted the handle is invalidated and only methodAddressableHeap.Handle.getKey()
andAddressableHeap.Handle.getValue()
can be used.- Specified by:
deleteMin
in interfaceAddressableHeap<K,
V> - Returns:
- a handle to the deleted element with minimum key
-
checkCapacity
protected final void checkCapacity(int capacity) -
ensureCapacity
protected abstract void ensureCapacity(int capacity) -
forceFixup
protected abstract void forceFixup(int k) -
fixup
protected abstract void fixup(int k) -
fixupWithComparator
protected abstract void fixupWithComparator(int k) -
fixdown
protected abstract void fixdown(int k) -
fixdownWithComparator
protected abstract void fixdownWithComparator(int k)
-