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 Summary

    Fields
    Modifier and Type
    Field
    Description
    protected static final int
    DEFAULT_CAPACITY
    The default heap capacity

  • Constructor Summary

    Constructors
    Constructor
    Description
    BinaryHeap(Comparator<T> comparator)
    Create an BinaryHeap<T> with a custom comparator.
    BinaryHeap(Comparator<T> comparator, int capacity)
    Create an BinaryHeap<T> with a custom comparator and capacity.

  • Method Summary

    Modifier and Type
    Method
    Description
    Comparator<T>
    comparator()
    Get the comparator used to order items in this heap.
    static <T extends Comparable<T>>
    BinaryHeap<T>
    createComparable()
    Create an BinaryHeap<T> with natural order comparator in a type safe way.
    static <T extends Comparable<T>>
    BinaryHeap<T>
    createComparable(int capacity)
    Create an BinaryHeap<T> with natural order comparator in a type safe way.
    protected Object[]
    getItems()
     
    protected static <T> void
    heapifyDown(Object[] items, Comparator<T> comparator, int i, int size)
    Heapify down implementation
    protected static <T> void
    heapifyUp(Object[] items, Comparator<T> comparator, int i)
    Heapify up implementation
    boolean
    isEmpty()
    Checks if the heap is empty.
    BinaryHeap<T>
    mergeWith(Heap<T> other)
    Merges this heap with the other using this.Heap.comparator().
    T
    peek()
    Retrieves the best element of the heap without removing it.
    T
    pop()
    Removes and retrieves the best element of the heap, and ensures that the heap property is maintained after removal.
    int
    push(T item)
    Inserts an element into the heap and ensures that the minimum heap property is maintained.
    void
    restoreHeapOrder()
    Restores the minimum heap property of the binary heap after modifications to its elements.
    int
    size()
    Gets the number of elements currently stored in the heap.
    String
    toString()
     

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

  • Field Details

    • DEFAULT_CAPACITY

      protected static final int DEFAULT_CAPACITY
      The default heap capacity
      See Also:

  • 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
      Returns:
      a comparable heap with default capacity

    • 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
      Returns:
      a comparable heap with given 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)
      Heapify down implementation
      Type Parameters:
      T - value type
      Parameters:
      items - array
      comparator - comparator
      i - current index
      size - size of heap

    • heapifyUp

      protected static <T> void heapifyUp(Object[] items, Comparator<T> comparator, int i)
      Heapify up implementation
      Type Parameters:
      T - value type
      Parameters:
      items - array
      comparator - comparator
      i - current index