Class AbstractRadixHeap<K>

    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected java.util.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 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 long serialVersionUID  
      protected long size
      Number of elements
    • Constructor Summary

      Constructors 
      Constructor Description
      AbstractRadixHeap()
      Constructor
    • Method Summary

      All Methods Instance Methods Abstract Methods Concrete Methods 
      Modifier and Type Method Description
      void clear()
      Clear all the elements of this heap.
      java.util.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 java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • EMPTY

        protected static final int EMPTY
        Denotes that a key does not belong to a bucket
        See Also:
        Constant Field Values
      • buckets

        protected java.util.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 Detail

      • AbstractRadixHeap

        AbstractRadixHeap()
        Constructor
    • Method Detail

      • 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:
        java.lang.IllegalArgumentException - if the key is null
        java.lang.IllegalArgumentException - if the key is less than the minimum allowed key
        java.lang.IllegalArgumentException - if the key is more than the maximum allowed key
        java.lang.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 java.util.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