Package org.jheaps.monotone
Class BigIntegerRadixAddressableHeap<V>
java.lang.Object
org.jheaps.monotone.AbstractRadixAddressableHeap<BigInteger,V>
org.jheaps.monotone.BigIntegerRadixAddressableHeap<V>
- Type Parameters:
V
- the type of values maintained by this heap
- All Implemented Interfaces:
Serializable
,AddressableHeap<BigInteger,
V>
An addressable radix heap for
BigInteger
keys. The heap stores
BigInteger
keys sorted according to the natural ordering of its keys. A radix heap is a monotone heap, especially
designed for algorithms (such as Dijkstra) which scan elements in order of
nondecreasing keys.
The implementation use arrays in order to store the elements. Operations
insert
and findMin
are worst-case constant time. The cost of
operation deleteMin
is amortized O(logC) assuming the radix-heap
contains keys in the range [0, C] or equivalently
[a,a+C].
Note that this implementation is not synchronized. If multiple threads access a heap concurrently, and at least one of the threads modifies the heap structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more elements or changing the key of some element.) This is typically accomplished by synchronizing on some object that naturally encapsulates the heap.
- See Also:
-
Nested Class Summary
Nested classes/interfaces inherited from class org.jheaps.monotone.AbstractRadixAddressableHeap
AbstractRadixAddressableHeap.Node
Nested classes/interfaces inherited from interface org.jheaps.AddressableHeap
AddressableHeap.Handle<K,
V> -
Field Summary
FieldsFields inherited from class org.jheaps.monotone.AbstractRadixAddressableHeap
buckets, currentMin, EMPTY, lastDeletedKey, maxKey, minKey, size
-
Constructor Summary
ConstructorsConstructorDescriptionBigIntegerRadixAddressableHeap
(BigInteger minKey, BigInteger maxKey) Constructs a new heap which can store values between a minimum and a maximum key value (inclusive). -
Method Summary
Modifier and TypeMethodDescriptionprotected int
compare
(BigInteger o1, BigInteger o2) Compares its two arguments for order.protected int
msd
(BigInteger a, BigInteger b) Compute the most significant digit which is different in the binary representation of two values, or -1 if numbers are equal.Methods inherited from class org.jheaps.monotone.AbstractRadixAddressableHeap
clear, comparator, computeBucket, deleteMin, findMin, insert, insert, isEmpty, size
-
Field Details
-
serialVersionUID
private static final long serialVersionUID- See Also:
-
-
Constructor Details
-
BigIntegerRadixAddressableHeap
Constructs a new heap which can store values between a minimum and a maximum key value (inclusive). It is important to use the smallest key range as the heap uses O(logC) where C=maxKey-minKey+1 buckets to store elements. Moreover, the operationdeleteMin
requires amortized O(logC) time.- Parameters:
minKey
- the non-negative minimum key that this heap supports (inclusive)maxKey
- the maximum key that this heap supports (inclusive)- Throws:
IllegalArgumentException
- if the minimum key is negativeIllegalArgumentException
- if the maximum key is less than the minimum key
-
-
Method Details
-
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.- Specified by:
compare
in classAbstractRadixAddressableHeap<BigInteger,
V> - 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.
-
msd
Compute the most significant digit which is different in the binary representation of two values, or -1 if numbers are equal.- Specified by:
msd
in classAbstractRadixAddressableHeap<BigInteger,
V> - Parameters:
a
- the first valueb
- the second value- Returns:
- the most significant digit which is different or -1 if numbers are equal
-