Package com.abstractkamen.datastructures.impl.heaps

Class BinaryHeap<T>

java.lang.Object
com.abstractkamen.datastructures.impl.heaps.BinaryHeap<T>
Type Parameters:
T - The type of elements stored in the binary heap.
All Implemented Interfaces:
Heap<T>, MergeableHeap<T>
Direct Known Subclasses:
AdjustableBinaryHeap
public class BinaryHeap<T> extends Object implements Heap<T>, MergeableHeap<T>
The elements of the binary heap are ordered according to their natural ordering, or by a Comparator provided at construction time, depending on which constructor is used. This implementation does not permit null elements.

  • Field Details

  • Constructor Details

    • BinaryHeap

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

    • BinaryHeap

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

  • Method Details

    • createComparable

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

    • createComparable

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

    • size

      public int size()
      Description copied from interface: Heap
      Gets the number of elements currently stored in the heap.
      Specified by:
      size in interface Heap<T>
      Returns:
      The size of the heap.

    • isEmpty

      public boolean isEmpty()
      Description copied from interface: Heap
      Checks if the heap is empty.
      Specified by:
      isEmpty in interface Heap<T>
      Returns:
      true if the heap is empty, false otherwise.

    • push

      public int push(T item)
      Description copied from interface: Heap
      Inserts an element into the heap and ensures that the minimum heap property is maintained.
      Specified by:
      push in interface Heap<T>
      Parameters:
      item - The element to be inserted.
      Returns:
      The new size of the heap after insertion.

    • peek

      public T peek()
      Description copied from interface: Heap
      Retrieves the best element of the heap without removing it.
      Specified by:
      peek in interface Heap<T>
      Returns:
      The best element of the heap, or null if the heap is empty.

    • pop

      public T pop()
      Description copied from interface: Heap
      Removes and retrieves the best element of the heap, and ensures that the heap property is maintained after removal.
      Specified by:
      pop in interface Heap<T>
      Returns:
      The best element of the heap.

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • comparator

      public Comparator<T> comparator()
      Description copied from interface: Heap
      Get the comparator used to order items in this heap.
      Specified by:
      comparator in interface Heap<T>
      Returns:
      The comparator used to order items in this heap. Never null.

    • mergeWith

      public BinaryHeap<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>
      Parameters:
      other - heap
      Returns:
      this merged with other

    • restoreHeapOrder

      public void restoreHeapOrder()
      Restores the minimum heap property of the binary heap after modifications to its elements. This method should be called when some elements' keys are mutated to ensure that the minimum heap property is maintained throughout the binary heap.

      The method traverses the binary heap from the last parent node to the root, applying the heapifyDown operation to each node. This process rearranges the elements to satisfy the minimum heap property, considering the updated keys.

      Note: This method assumes that the comparator used to create the binary heap is consistent with the keys of the elements, and the elements are unique based on their keys.

    • getItems

      protected Object[] getItems()

    • heapifyDown

      protected static <T> void heapifyDown(Object[] items, Comparator<T> comparator, int i, int size)

    • heapifyUp

      protected static <T> void heapifyUp(Object[] items, Comparator<T> comparator, int i)