Package org.jheaps.array

Class AbstractArrayWeakHeap<K>

java.lang.Object
org.jheaps.array.AbstractArrayWeakHeap<K>
Type Parameters:
K - the type of keys maintained by this heap
All Implemented Interfaces:
Serializable, Heap<K>
Direct Known Subclasses:
AbstractArrayHeap, BinaryArrayWeakHeap
abstract class AbstractArrayWeakHeap<K> extends Object implements Heap<K>, 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 final 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 final int
    DOWNSIZING_MIN_HEAP_CAPACITY
    Limit for the heap capacity when down-sizing.
    protected static final int
    MAX_HEAP_CAPACITY
    The maximum heap capacity.
    protected static final int
    MIN_HEAP_CAPACITY
    The minimum heap capacity.
    protected final int
    minCapacity
    Minimum capacity due to initially requested capacity.
    private static final long
    serialVersionUID
     
    protected int
    size
    Number of elements in the heap.

  • Constructor Summary

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

  • Method Summary

    Modifier and Type
    Method
    Description
    protected final void
    checkCapacity(int capacity)
    Check that a capacity is valid.
    void
    clear()
    Clear all the elements of this heap.
    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

    Methods inherited from interface org.jheaps.Heap

    deleteMin, findMin, insert

  • Field Details

    • serialVersionUID

      private static final long serialVersionUID
      See Also:

    • MAX_HEAP_CAPACITY

      protected static final int MAX_HEAP_CAPACITY
      The maximum heap capacity.
      See Also:

    • MIN_HEAP_CAPACITY

      protected static final int MIN_HEAP_CAPACITY
      The minimum heap capacity.
      See Also:

    • DOWNSIZING_MIN_HEAP_CAPACITY

      protected static final int DOWNSIZING_MIN_HEAP_CAPACITY
      Limit for the heap capacity when down-sizing.
      See Also:

    • comparator

      protected final 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 Details

    • AbstractArrayWeakHeap

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

  • Method Details

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