Class BinaryMinHeap<E,K>

java.lang.Object
rgu.transport.algorithms.collections.BinaryMinHeap<E,K>
Type Parameters:
E - the type of elements, must be a hashable type
K - the type of key (also called priority)
All Implemented Interfaces:
MinHeap<E,K>
public final class BinaryMinHeap<E,K> extends Object implements MinHeap<E,K>
A minimum heap implemented as a binary heap. All mutations are O(log n). Not safe for concurrent use.
Author:
Lee A. Christie

  • Constructor Details

    • BinaryMinHeap

      public BinaryMinHeap(BiPredicate<K,K> lessThan)
      Constructs a new BinaryMinHeap.
      Parameters:
      lessThan - a pure predicate which tests whether a < b, not null

  • Method Details

    • isEmpty

      public boolean isEmpty()
      Returns true if this heap contains no elements.
      Specified by:
      isEmpty in interface MinHeap<E,K>
      Returns:
      true if this heap contains no elements

    • addElement

      public void addElement(E element, K key)
      Adds the specified element with the specified key.
      Specified by:
      addElement in interface MinHeap<E,K>
      Parameters:
      element - the element, not null
      key - the key, not null
      Throws:
      IllegalStateException - if the element already exists

    • decreaseKey

      public void decreaseKey(E element, K key)
      Replaces the key of the specified element with a specified smaller value.
      Specified by:
      decreaseKey in interface MinHeap<E,K>
      Parameters:
      element - the element, not null
      key - the new, smaller key value, not null
      Throws:
      IllegalStateException - if the new key is not smaller than the current key
      NoSuchElementException - if the element does not exist in the heap

    • deleteMinimum

      public E deleteMinimum()
      Removes and returns the element with the minimum key.
      Specified by:
      deleteMinimum in interface MinHeap<E,K>
      Returns:
      the element with the minimum value
      Throws:
      NoSuchElementException - if the heap is empty

    • toString

      public String toString()
      Returns a string representation of this heap. The order of elements is unspecified.
      Specified by:
      toString in interface MinHeap<E,K>
      Overrides:
      toString in class Object
      Returns:
      a string representation of this heap