Class AbstractRadixHeap<K>

java.lang.Object
org.jheaps.monotone.AbstractRadixHeap<K>
Type Parameters:
K - the key type
All Implemented Interfaces:
Serializable, Heap<K>
Direct Known Subclasses:
BigIntegerRadixHeap, DoubleRadixHeap, IntegerRadixHeap, LongRadixHeap
abstract class AbstractRadixHeap<K> extends Object implements Heap<K>, Serializable
Base abstract implementation of a radix heap.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected 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 final int
    EMPTY
    Denotes that a key does not belong to a bucket
    protected K
    lastDeletedKey
    Last deleted key.
    protected K
    maxKey
    Maximum key allowed
    protected K
    minKey
    Minimum key allowed
    private static final long
    serialVersionUID
     
    protected long
    size
    Number of elements

  • Constructor Summary

    Constructors
    Constructor
    Description
    AbstractRadixHeap()
    Constructor

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    clear()
    Clear all the elements of this heap.
    Comparator<? super K>
    comparator()
    Always returns null 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()
    Returns true 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.

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

    • serialVersionUID

      private static final long serialVersionUID
      See Also:

    • EMPTY

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

    • buckets

      protected 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 the minKey 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

  • Constructor Details

    • AbstractRadixHeap

      AbstractRadixHeap()
      Constructor

  • Method Details

    • findMin

      public K findMin()
      Find an element with the minimum key.
      Specified by:
      findMin in interface Heap<K>
      Returns:
      an element with the minimum key

    • insert

      public void insert(K key)
      Insert a key into the heap.
      Specified by:
      insert in interface Heap<K>
      Parameters:
      key - the key to insert
      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 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].
      Specified by:
      deleteMin in interface Heap<K>
      Returns:
      the deleted element with the minimum key

    • isEmpty

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

    • size

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

    • clear

      public void clear()
      Clear all the elements of this heap.
      Specified by:
      clear in interface Heap<K>

    • comparator

      public Comparator<? super K> comparator()
      Always returns null since this heap uses the natural ordering of its keys.
      Specified by:
      comparator in interface Heap<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 key
      minKey - 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 value
      b - 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