Package org.jheaps.monotone
Class AbstractRadixHeap<K>
- java.lang.Object
-
- org.jheaps.monotone.AbstractRadixHeap<K>
-
- Type Parameters:
K
- the key type
- All Implemented Interfaces:
java.io.Serializable
,Heap<K>
- Direct Known Subclasses:
BigIntegerRadixHeap
,DoubleRadixHeap
,IntegerRadixHeap
,LongRadixHeap
abstract class AbstractRadixHeap<K> extends java.lang.Object implements Heap<K>, java.io.Serializable
Base abstract implementation of a radix heap.
-
-
Field Summary
Fields Modifier and Type Field Description protected java.util.List<K>[]
buckets
The buckets as lists.protected K
currentMin
The current minimum value (cached)protected int
currentMinBucket
The current minimum value bucket (cached)protected int
currentMinPos
The current minimum value position in bucket (cached)protected static int
EMPTY
Denotes that a key does not belong to a bucketprotected K
lastDeletedKey
Last deleted key.protected K
maxKey
Maximum key allowedprotected K
minKey
Minimum key allowedprivate static long
serialVersionUID
protected long
size
Number of elements
-
Constructor Summary
Constructors Constructor Description AbstractRadixHeap()
Constructor
-
Method Summary
All Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description void
clear()
Clear all the elements of this heap.java.util.Comparator<? super K>
comparator()
Always returnsnull
since this heap uses the natural ordering of its keys.protected abstract int
compare(K o1, K o2)
Compares its two arguments for order.protected int
computeBucket(K key, K minKey)
Compute the bucket of a key based on a minimum key.K
deleteMin()
Delete and return an element with the minimum key.private void
findAndCacheMinimum(int firstBucket)
Helper method for finding and caching the minimum.K
findMin()
Find an element with the minimum key.void
insert(K key)
Insert a key into the heap.boolean
isEmpty()
Returnstrue
if this heap is empty.protected abstract int
msd(K a, K b)
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 Detail
-
serialVersionUID
private static final long serialVersionUID
- See Also:
- Constant Field Values
-
EMPTY
protected static final int EMPTY
Denotes that a key does not belong to a bucket- See Also:
- Constant Field Values
-
buckets
protected java.util.List<K>[] buckets
The buckets as lists. We use array-lists instead of linked-lists, to be cache friendly.
-
size
protected long size
Number of elements
-
lastDeletedKey
protected K lastDeletedKey
Last deleted key. This value is used to distribute elements in the buckets. Should be initialized with theminKey
value.
-
currentMin
protected K currentMin
The current minimum value (cached)
-
currentMinBucket
protected int currentMinBucket
The current minimum value bucket (cached)
-
currentMinPos
protected int currentMinPos
The current minimum value position in bucket (cached)
-
minKey
protected K minKey
Minimum key allowed
-
maxKey
protected K maxKey
Maximum key allowed
-
-
Method Detail
-
findMin
public K findMin()
Find an element with the minimum key.
-
insert
public void insert(K key)
Insert a key into the heap.- Specified by:
insert
in interfaceHeap<K>
- Parameters:
key
- the key to insert- Throws:
java.lang.IllegalArgumentException
- if the key is nulljava.lang.IllegalArgumentException
- if the key is less than the minimum allowed keyjava.lang.IllegalArgumentException
- if the key is more than the maximum allowed keyjava.lang.IllegalArgumentException
- if the key is less than the last deleted key (or the minimum key allowed if no key has been deleted)
-
deleteMin
public K 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
public java.util.Comparator<? super K> 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
protected abstract int compare(K o1, K o2)
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
protected int computeBucket(K key, K minKey)
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
protected abstract int msd(K a, K b)
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
-
-