Package org.jheaps.array

Class AbstractArrayWeakHeap<K>

  • Type Parameters:
    K - the type of keys maintained by this heap
    All Implemented Interfaces:
    java.io.Serializable, Heap<K>
    Direct Known Subclasses:
    AbstractArrayHeap, BinaryArrayWeakHeap
    abstract class AbstractArrayWeakHeap<K>
extends java.lang.Object
implements Heap<K>, java.io.Serializable
    An abstract weak heap with an array representation.

    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected K[] array
      The array used for representing the heap.
      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.
      protected static int DOWNSIZING_MIN_HEAP_CAPACITY
      Limit for the heap capacity when down-sizing.
      protected static int MAX_HEAP_CAPACITY
      The maximum heap capacity.
      protected static int MIN_HEAP_CAPACITY
      The minimum heap capacity.
      protected int minCapacity
      Minimum capacity due to initially requested capacity.
      private static long serialVersionUID  
      protected int size
      Number of elements in the heap.

    • Constructor Summary

      Constructors 
      Constructor Description
      AbstractArrayWeakHeap​(java.util.Comparator<? super K> comparator, int capacity)
      Constructor

    • Method Summary

      All Methods Instance Methods Abstract Methods Concrete Methods 
      Modifier and Type Method Description
      protected void checkCapacity​(int capacity)
      Check that a capacity is valid.
      void clear()
      Clear all the elements of this heap.
      java.util.Comparator<? super K> comparator()
      Returns the comparator used to order the keys in this heap, or null if this heap uses the natural ordering of its keys.
      protected abstract void ensureCapacity​(int capacity)
      Make sure the array representation can hold a certain number of elements.
      protected abstract void fixdown​(int k)
      Downwards fix starting from a particular element
      protected abstract void fixdownWithComparator​(int k)
      Downwards fix starting from a particular element.
      protected abstract void fixup​(int k)
      Upwards fix starting from a particular element
      protected abstract void fixupWithComparator​(int k)
      Upwards fix starting from a particular element.
      protected abstract void initCapacity​(int capacity)
      Initialize array representation.
      boolean isEmpty()
      Returns true if this heap is empty.
      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

      • 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 final 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.

      • array

        protected K[] array
        The array used for representing the heap.

      • size

        protected int size
        Number of elements in the heap.

      • minCapacity

        protected final int minCapacity
        Minimum capacity due to initially requested capacity.

    • Constructor Detail

      • AbstractArrayWeakHeap

        public AbstractArrayWeakHeap​(java.util.Comparator<? super K> comparator,
                             int capacity)
        Constructor
        Parameters:
        comparator - the comparator to use
        capacity - the requested capacity

    • Method Detail

      • 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

      • comparator

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

      • clear

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

      • checkCapacity

        protected final void checkCapacity​(int capacity)
        Check that a capacity is valid.
        Parameters:
        capacity - the capacity
        Throws:
        java.lang.IllegalArgumentException - if the capacity is negative or more than the maximum array size

      • initCapacity

        protected abstract void initCapacity​(int capacity)
        Initialize array representation.
        Parameters:
        capacity - the capacity

      • ensureCapacity

        protected abstract void ensureCapacity​(int capacity)
        Make sure the array representation can hold a certain number of elements.
        Parameters:
        capacity - the capacity

      • fixup

        protected abstract void fixup​(int k)
        Upwards fix starting from a particular element
        Parameters:
        k - the index of the starting element

      • fixupWithComparator

        protected abstract void fixupWithComparator​(int k)
        Upwards fix starting from a particular element. Performs comparisons using the comparator.
        Parameters:
        k - the index of the starting element

      • fixdown

        protected abstract void fixdown​(int k)
        Downwards fix starting from a particular element
        Parameters:
        k - the index of the starting element

      • fixdownWithComparator

        protected abstract void fixdownWithComparator​(int k)
        Downwards fix starting from a particular element. Performs comparisons using the comparator.
        Parameters:
        k - the index of the starting element