Package org.jheaps.monotone

Class BigIntegerRadixAddressableHeap<V>

  • Type Parameters:
    V - the type of values maintained by this heap
    All Implemented Interfaces:
    Serializable, AddressableHeap<BigInteger,​V>
    public class BigIntegerRadixAddressableHeap<V>
extends Object
    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.

    Author:
    Dimitrios Michail
    See Also:
    AddressableHeap, Serialized Form

    • Constructor Detail

      • BigIntegerRadixAddressableHeap

        public BigIntegerRadixAddressableHeap​(BigInteger minKey,
                                      BigInteger maxKey)
        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 operation deleteMin 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 negative
        IllegalArgumentException - if the maximum key is less than the minimum key