Package org.jheaps.monotone

Class IntegerRadixAddressableHeap<V>

java.lang.Object
org.jheaps.monotone.IntegerRadixAddressableHeap<V>
Type Parameters:
V - the type of values maintained by this heap
All Implemented Interfaces:
Serializable, AddressableHeap<Integer,V>
public class IntegerRadixAddressableHeap<V> extends Object
An addressable radix heap for (signed) integer keys. The heap stores integer 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 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]. This implementation views integer values as signed numbers.

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:

  • Field Details

    • EMPTY

      protected static final int EMPTY
      Denotes that a key does not belong to a bucket
      See Also:

    • buckets

      protected org.jheaps.monotone.AbstractRadixAddressableHeap<Integer,V>.org.jheaps.monotone.AbstractRadixAddressableHeap.Node[] buckets
      The buckets as lists.

    • size

      protected long size
      Number of elements

    • lastDeletedKey

      protected Integer lastDeletedKey
      Last deleted key. This value is used to distribute elements in the buckets. Should be initialized with the minKey value.

    • currentMin

      protected org.jheaps.monotone.AbstractRadixAddressableHeap<Integer,V>.org.jheaps.monotone.AbstractRadixAddressableHeap.Node currentMin
      The current minimum value (cached)

    • minKey

      protected Integer minKey
      Minimum key allowed

    • maxKey

      protected Integer maxKey
      Maximum key allowed

  • Constructor Details

    • IntegerRadixAddressableHeap

      public IntegerRadixAddressableHeap(int minKey, int 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

  • Method Details

    • compare

      protected int compare(Integer o1, Integer 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.

    • msd

      protected int msd(Integer a, Integer 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 value
      b - the second value
      Returns:
      the most significant digit which is different or -1 if numbers are equal

    • findMin

      public AddressableHeap.Handle<Integer,V> findMin()
      Find an element with the minimum key.
      Specified by:
      findMin in interface AddressableHeap<K,V>
      Returns:
      a handle to an element with minimum key

    • insert

      public AddressableHeap.Handle<Integer,V> insert(Integer key)
      Insert a new element into the heap with a null value.
      Specified by:
      insert in interface AddressableHeap<K,V>
      Parameters:
      key - the element's key
      Returns:
      a handle for the newly added element
      Throws:
      IllegalArgumentException - if the key is null
      IllegalArgumentException - if the key is less than the minimum allowed key
      IllegalArgumentException - if the key is more than the maximum allowed key
      IllegalArgumentException - if the key is less than the last deleted key (or the minimum key allowed if no key has been deleted)

    • insert

      public AddressableHeap.Handle<Integer,V> insert(Integer key, V value)
      Insert a new element into the heap.
      Specified by:
      insert in interface AddressableHeap<K,V>
      Parameters:
      key - the element's key
      value - the element's value
      Returns:
      a handle for the newly added element
      Throws:
      IllegalArgumentException - if the key is null
      IllegalArgumentException - if the key is less than the minimum allowed key
      IllegalArgumentException - if the key is more than the maximum allowed key
      IllegalArgumentException - if the key is less than the last deleted key (or the minimum key allowed if no key has been deleted)

    • deleteMin

      public AddressableHeap.Handle<Integer,V> deleteMin()
      Delete and return an element with the minimum key. If multiple such elements exists, only one of them will be deleted. After the element is deleted the handle is invalidated and only method AddressableHeap.Handle.getKey() and AddressableHeap.Handle.getValue() can be used. The cost of this operation is amortized O(logC) assuming the heap contains keys in the range [0, C] or equivalently [a, a+C].
      Specified by:
      deleteMin in interface AddressableHeap<K,V>
      Returns:
      a handle to the deleted element with minimum key

    • isEmpty

      public boolean isEmpty()
      Returns true if this heap is empty.
      Specified by:
      isEmpty in interface AddressableHeap<K,V>
      Returns:
      true if this heap is empty, false otherwise

    • size

      public long size()
      Returns the number of elements in the heap.
      Specified by:
      size in interface AddressableHeap<K,V>
      Returns:
      the number of elements in the heap

    • clear

      public void clear()
      Clear all the elements of the heap. After calling this method all handles should be considered invalidated and the behavior of methods AddressableHeap.Handle.decreaseKey(Object) and AddressableHeap.Handle.delete() is undefined.
      Specified by:
      clear in interface AddressableHeap<K,V>

    • comparator

      public Comparator<? super Integer> comparator()
      Always returns null since this heap uses the natural ordering of its keys.
      Specified by:
      comparator in interface AddressableHeap<K,V>
      Returns:
      null since this heap uses the natural ordering of its keys

    • computeBucket

      protected int computeBucket(Integer key, Integer minKey)
      Compute the bucket of a key based on a minimum key.
      Parameters:
      key - the key
      minKey - the minimum key
      Returns:
      the bucket where the key should go