Class DoubleRadixHeap

  • All Implemented Interfaces:
    java.io.Serializable, Heap<java.lang.Double>

    public class DoubleRadixHeap
    extends AbstractRadixHeap<java.lang.Double>
    A radix heap for double keys. The heap stores double 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.

    Note that this implementation uses the fact that the IEEE floating-point standard has the property that for any valid floating-point numbers a and b, a<=b if and only if bits(a)<= bits(b), where bits(x) denotes the re-interpretation of x as an unsigned integer (long in our case).

    This implementation uses 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, however, that C here depends on the distance of the minimum and maximum value when they are translated into unsigned longs.

    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:
    Serialized Form
    • Constructor Detail

      • DoubleRadixHeap

        public DoubleRadixHeap​(double minKey,
                               double 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:
        java.lang.IllegalArgumentException - if the minimum key is negative
        java.lang.IllegalArgumentException - if the maximum key is less than the minimum key
    • Method Detail

      • compare

        protected int compare​(java.lang.Double o1,
                              java.lang.Double 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.
        Specified by:
        compare in class AbstractRadixHeap<java.lang.Double>
        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

        protected int msd​(java.lang.Double a,
                          java.lang.Double b)
        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 class AbstractRadixHeap<java.lang.Double>
        Parameters:
        a - the first value
        b - the second value
        Returns:
        the most significant digit which is different or -1 if numbers are equal