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:
java.io.Serializable
,AddressableHeap<K,V>
- Direct Known Subclasses:
BinaryArrayAddressableHeap
,DaryArrayAddressableHeap
abstract class AbstractArrayAddressableHeap<K,V> extends java.lang.Object implements AddressableHeap<K,V>, java.io.Serializable
Abstract implementation of a heap using an array representation.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description protected class
AbstractArrayAddressableHeap.ArrayHandle
-
Nested classes/interfaces inherited from interface org.jheaps.AddressableHeap
AddressableHeap.Handle<K,V>
-
-
Field Summary
Fields Modifier and Type Field Description protected AbstractArrayAddressableHeap.ArrayHandle[]
array
The array use for representing the tree.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.protected static int
NO_INDEX
Denotes that a handle is not in the arrayprivate static long
serialVersionUID
protected int
size
Number of elements in the heap.
-
Constructor Summary
Constructors Constructor Description AbstractArrayAddressableHeap(java.util.Comparator<? super K> comparator, int capacity)
-
Method Summary
All Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description protected void
checkCapacity(int capacity)
void
clear()
Clear all the elements of the heap.java.util.Comparator<? super K>
comparator()
Returns the comparator used to order the keys in this AddressableHeap, ornull
if this heap uses the natural ordering of its keys.AddressableHeap.Handle<K,V>
deleteMin()
Delete and return an element with the minimum key.protected abstract void
ensureCapacity(int capacity)
AddressableHeap.Handle<K,V>
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)
AddressableHeap.Handle<K,V>
insert(K key)
Insert a new element into the heap with a null value.AddressableHeap.Handle<K,V>
insert(K key, V 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 Detail
-
serialVersionUID
private static final long serialVersionUID
- See Also:
- Constant Field Values
-
NO_INDEX
protected static final int NO_INDEX
Denotes that a handle is not in the array- 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 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 AbstractArrayAddressableHeap.ArrayHandle[] array
The array use for representing the tree.
-
size
protected int size
Number of elements in the heap.
-
minCapacity
protected final int minCapacity
Minimum capacity due to initially requested capacity.
-
-
Constructor Detail
-
AbstractArrayAddressableHeap
public AbstractArrayAddressableHeap(java.util.Comparator<? super K> comparator, int capacity)
-
-
Method Detail
-
findMin
public AddressableHeap.Handle<K,V> 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
public java.util.Comparator<? super K> 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
public AddressableHeap.Handle<K,V> insert(K key)
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
public AddressableHeap.Handle<K,V> insert(K key, V value)
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
public AddressableHeap.Handle<K,V> 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)
-
-