Package com.abstractkamen.datastructures.impl.heaps

Class AdjustableBinaryHeap<T>

java.lang.Object
com.abstractkamen.datastructures.impl.heaps.BinaryHeap<T>
com.abstractkamen.datastructures.impl.heaps.AdjustableBinaryHeap<T>
Type Parameters:
T - The type of elements stored in the heap, must be comparable.
All Implemented Interfaces:
AdjustableHeap<T>, Heap<T>, MergeableHeap<T>
public class AdjustableBinaryHeap<T> extends BinaryHeap<T> implements Heap<T>, MergeableHeap<T>, AdjustableHeap<T>
An implementation of an adjustable binary heap data structure.
See Also:

  • Constructor Details

    • AdjustableBinaryHeap

      public AdjustableBinaryHeap(Comparator<T> comparator)
      Create an AdjustableBinaryHeap<T> with a custom comparator
      Parameters:
      comparator - custom comparator

    • AdjustableBinaryHeap

      public AdjustableBinaryHeap(Comparator<T> comparator, int capacity)
      Create an AdjustableBinaryHeap<T> with a custom comparator
      Parameters:
      capacity - initial capacity
      comparator - custom comparator

  • Method Details

    • createComparable

      public static <T extends Comparable<T>> AdjustableBinaryHeap<T> createComparable()
      Create an AdjustableBinaryHeap<T> with natural order comparator in a type safe way.
      Type Parameters:
      T - comparable type

    • createComparable

      public static <T extends Comparable<T>> AdjustableBinaryHeap<T> createComparable(int capacity)
      Create an AdjustableBinaryHeap<T> with natural order comparator in a type safe way.
      Type Parameters:
      T - comparable type
      Parameters:
      capacity - initial capacity

    • increaseKey

      public boolean increaseKey(T item, T increasedItem)
      Description copied from interface: AdjustableHeap
      Try to increase item if it's present in this heap.
      Specified by:
      increaseKey in interface AdjustableHeap<T>
      Parameters:
      item - to be increased
      increasedItem - increasing item
      Returns:
      true if item is present and successfully increased

    • decreaseKey

      public boolean decreaseKey(T item, T decreasedItem)
      Description copied from interface: AdjustableHeap
      Try to decrease item if it's present in this heap.
      Specified by:
      decreaseKey in interface AdjustableHeap<T>
      Parameters:
      item - to be decreased
      decreasedItem - decreasing item
      Returns:
      true if item is present and successfully decreased

    • mergeWith

      public AdjustableBinaryHeap<T> mergeWith(Heap<T> other)
      Description copied from interface: MergeableHeap
      Merges this heap with the other using this.Heap.comparator(). The heaps will be merged regardless of other 's order. Depending on the implementation this may have an impact on performance. 
       Example:
     MergeableHeap<Heap<Integer>> a = new SomeMergeableHeapImpl(Integer::compare);
     // can be merged with
     MergeableHeap<Heap<Integer>> b = new SomeMergeableHeapImpl(Comparator.reverseOrder(Integer::compare));
     // different implementations will have different time complexity
     a.mergeWith(b);
      Specified by:
      mergeWith in interface MergeableHeap<T>
      Overrides:
      mergeWith in class BinaryHeap<T>
      Parameters:
      other - heap
      Returns:
      this merged with other