Package org.jheaps.monotone
Class AbstractRadixHeap<K>
java.lang.Object
org.jheaps.monotone.AbstractRadixHeap<K>
- Type Parameters:
K
- the key type
- All Implemented Interfaces:
Serializable
,Heap<K>
- Direct Known Subclasses:
BigIntegerRadixHeap
,DoubleRadixHeap
,IntegerRadixHeap
,LongRadixHeap
Base abstract implementation of a radix heap.
-
Field Summary
FieldsModifier and TypeFieldDescriptionThe buckets as lists.protected K
The current minimum value (cached)protected int
The current minimum value bucket (cached)protected int
The current minimum value position in bucket (cached)protected static final int
Denotes that a key does not belong to a bucketprotected K
Last deleted key.protected K
Maximum key allowedprotected K
Minimum key allowedprivate static final long
protected long
Number of elements -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionvoid
clear()
Clear all the elements of this heap.Comparator<? super K>
Always returnsnull
since this heap uses the natural ordering of its keys.protected abstract int
Compares its two arguments for order.protected int
computeBucket
(K key, K minKey) Compute the bucket of a key based on a minimum key.Delete and return an element with the minimum key.private void
findAndCacheMinimum
(int firstBucket) Helper method for finding and caching the minimum.findMin()
Find an element with the minimum key.void
Insert a key into the heap.boolean
isEmpty()
Returnstrue
if this heap is empty.protected abstract int
Compute the most significant digit which is different in the binary representation of two values, or -1 if numbers are equal.long
size()
Returns the number of elements in this heap.
-
Field Details
-
serialVersionUID
private static final long serialVersionUID- See Also:
-
EMPTY
protected static final int EMPTYDenotes that a key does not belong to a bucket- See Also:
-
buckets
The buckets as lists. We use array-lists instead of linked-lists, to be cache friendly. -
size
protected long sizeNumber of elements -
lastDeletedKey
Last deleted key. This value is used to distribute elements in the buckets. Should be initialized with theminKey
value. -
currentMin
The current minimum value (cached) -
currentMinBucket
protected int currentMinBucketThe current minimum value bucket (cached) -
currentMinPos
protected int currentMinPosThe current minimum value position in bucket (cached) -
minKey
Minimum key allowed -
maxKey
Maximum key allowed
-
-
Constructor Details
-
AbstractRadixHeap
AbstractRadixHeap()Constructor
-
-
Method Details
-
findMin
Find an element with the minimum key. -
insert
Insert a key into the heap.- Specified by:
insert
in interfaceHeap<K>
- Parameters:
key
- the key to insert- Throws:
IllegalArgumentException
- if the key is nullIllegalArgumentException
- if the key is less than the minimum allowed keyIllegalArgumentException
- if the key is more than the maximum allowed keyIllegalArgumentException
- if the key is less than the last deleted key (or the minimum key allowed if no key has been deleted)
-
deleteMin
Delete and return an element with the minimum key. If multiple such elements exists, only one of them will be deleted. The cost of this operation is amortized O(logC) assuming the heap contains keys in the range [0, C] or equivalently [a, a+C]. -
isEmpty
public boolean isEmpty()Returnstrue
if this heap is empty. -
size
public long size()Returns the number of elements in this heap. -
clear
public void clear()Clear all the elements of this heap. -
comparator
Always returnsnull
since this heap uses the natural ordering of its keys.- Specified by:
comparator
in interfaceHeap<K>
- Returns:
null
since this heap uses the natural ordering of its keys
-
compare
Compares its two arguments for order. Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.- Parameters:
o1
- the first object to be compared.o2
- the second object to be compared.- Returns:
- a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.
-
computeBucket
Compute the bucket of a key based on a minimum key.- Parameters:
key
- the keyminKey
- the minimum key- Returns:
- the bucket where the key should go
-
msd
Compute the most significant digit which is different in the binary representation of two values, or -1 if numbers are equal.- Parameters:
a
- the first valueb
- the second value- Returns:
- the most significant digit which is different or -1 if numbers are equal
-
findAndCacheMinimum
private void findAndCacheMinimum(int firstBucket) Helper method for finding and caching the minimum. Assumes that the heap contains at least one element.- Parameters:
firstBucket
- start looking for elements from this bucket
-