Class AbstractArrayAddressableHeap<K,​V>

  • Type Parameters:
    K - the type of keys maintained by this heap
    All Implemented Interfaces:
    java.io.Serializable, AddressableHeap<K,​V>
    Direct Known Subclasses:
    BinaryArrayAddressableHeap, DaryArrayAddressableHeap

    abstract class AbstractArrayAddressableHeap<K,​V>
    extends java.lang.Object
    implements AddressableHeap<K,​V>, java.io.Serializable
    Abstract implementation of a heap using an array representation.
    • Field Detail

      • NO_INDEX

        protected static final int NO_INDEX
        Denotes that a handle is not in the array
        See Also:
        Constant Field Values
      • MAX_HEAP_CAPACITY

        protected static final int MAX_HEAP_CAPACITY
        The maximum heap capacity.
        See Also:
        Constant Field Values
      • MIN_HEAP_CAPACITY

        protected static final int MIN_HEAP_CAPACITY
        The minimum heap capacity.
        See Also:
        Constant Field Values
      • DOWNSIZING_MIN_HEAP_CAPACITY

        protected static final int DOWNSIZING_MIN_HEAP_CAPACITY
        Limit for the heap capacity when down-sizing.
        See Also:
        Constant Field Values
      • comparator

        protected java.util.Comparator<? super K> comparator
        The comparator used to maintain order in this heap, or null if it uses the natural ordering of its keys.
      • size

        protected int size
        Number of elements in the heap.
      • minCapacity

        protected final int minCapacity
        Minimum capacity due to initially requested capacity.
    • Constructor Detail

      • AbstractArrayAddressableHeap

        public AbstractArrayAddressableHeap​(java.util.Comparator<? super K> comparator,
                                            int capacity)
    • Method Detail

      • 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
      • comparator

        public java.util.Comparator<? super K> comparator()
        Returns the comparator used to order the keys in this AddressableHeap, or null if this heap uses the natural ordering of its keys.
        Specified by:
        comparator in interface AddressableHeap<K,​V>
        Returns:
        the comparator used to order the keys in this heap, or null if this addressable heap uses the natural ordering of its keys
      • insert

        public AddressableHeap.Handle<K,​V> insert​(K 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
      • insert

        public AddressableHeap.Handle<K,​V> insert​(K 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
      • checkCapacity

        protected final void checkCapacity​(int capacity)
      • ensureCapacity

        protected abstract void ensureCapacity​(int capacity)
      • forceFixup

        protected abstract void forceFixup​(int k)
      • fixup

        protected abstract void fixup​(int k)
      • fixupWithComparator

        protected abstract void fixupWithComparator​(int k)
      • fixdown

        protected abstract void fixdown​(int k)
      • fixdownWithComparator

        protected abstract void fixdownWithComparator​(int k)