Interface MinHeap<E,K>

Type Parameters:
E - the type of elements, must be a hashable type
K - the type of key (also called priority)
All Known Implementing Classes:
BinaryMinHeap
public interface MinHeap<E,K>
A minimum heap priority queue. Elements in MinHeap are given a key (also called priority), which may be non-unique. This differs from PriorityQueue in the Java standard library in which Comparable or Comparator is used.

Elements with the minimum key are removed first. The key of an existing element may be decreased by calling the decreaseKey(Object, Object) method, which will throw an exception if the new key is not smaller.

Implementations are not required to support increasing the key of an existing element but may provide supplementary methods. Implementations are not required to be safe for concurrent use.

Author:
Lee A. Christie

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    addElement(E element, K key)
    Adds the specified element with the specified key.
    void
    decreaseKey(E element, K key)
    Replaces the key of the specified element with a specified smaller value.
    E
    deleteMinimum()
    Removes and returns the element with the minimum key.
    boolean
    isEmpty()
    Returns true if this heap contains no elements.
    String
    toString()
    Returns a string representation of this heap, typically used for debugging.

  • Method Details

    • isEmpty

      boolean isEmpty()
      Returns true if this heap contains no elements.
      Returns:
      true if this heap contains no elements

    • addElement

      void addElement(E element, K key)
      Adds the specified element with the specified key.
      Parameters:
      element - the element, not null
      key - the key, not null
      Throws:
      IllegalStateException - if the element already exists

    • decreaseKey

      void decreaseKey(E element, K key)
      Replaces the key of the specified element with a specified smaller value.
      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

      E deleteMinimum()
      Removes and returns the element with the minimum key.
      Returns:
      the element with the minimum value
      Throws:
      NoSuchElementException - if the heap is empty

    • toString

      String toString()
      Returns a string representation of this heap, typically used for debugging. The order of elements is unspecified and depends on the implementation.
      Overrides:
      toString in class Object
      Returns:
      a string representation of this heap