Package org.jheaps.array

Class AbstractArrayAddressableHeap<K,V>

java.lang.Object
org.jheaps.array.AbstractArrayAddressableHeap<K,V>
Type Parameters:
K - the type of keys maintained by this heap
All Implemented Interfaces:
Serializable, AddressableHeap<K,V>
Direct Known Subclasses:
BinaryArrayAddressableHeap, DaryArrayAddressableHeap
abstract class AbstractArrayAddressableHeap<K,V> extends Object implements AddressableHeap<K,V>, Serializable
Abstract implementation of a heap using an array representation.

  • Field Details

    • serialVersionUID

      private static final long serialVersionUID
      See Also:

    • NO_INDEX

      protected static final int NO_INDEX
      Denotes that a handle is not in the array
      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 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 AbstractArrayAddressableHeap<K,V>.ArrayHandle[] array
      The array use for representing the tree.

    • size

      protected int size
      Number of elements in the heap.

    • minCapacity

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

  • Constructor Details

    • AbstractArrayAddressableHeap

      public AbstractArrayAddressableHeap(Comparator<? super K> comparator, int capacity)

  • Method Details

    • findMin

      public AddressableHeap.Handle<K,V> findMin()
      Find an element with the minimum key.
      Specified by:
      findMin in interface AddressableHeap<K,V>
      Returns:
      a handle to an element with minimum key

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

    • clear

      public void clear()
      Clear all the elements of the heap. After calling this method all handles should be considered invalidated and the behavior of methods AddressableHeap.Handle.decreaseKey(Object) and AddressableHeap.Handle.delete() is undefined.
      Specified by:
      clear in interface AddressableHeap<K,V>

    • 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

    • deleteMin

      public AddressableHeap.Handle<K,V> deleteMin()
      Delete and return an element with the minimum key. If multiple such elements exists, only one of them will be deleted. After the element is deleted the handle is invalidated and only method AddressableHeap.Handle.getKey() and AddressableHeap.Handle.getValue() can be used.
      Specified by:
      deleteMin in interface AddressableHeap<K,V>
      Returns:
      a handle to the deleted element with minimum key

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