Module org.cicirello.core
Package org.cicirello.ds

Class BinaryHeapDouble<E>

java.lang.Object
org.cicirello.ds.BinaryHeapDouble<E>
Type Parameters:
E - The type of object contained in the BinaryHeapDouble.
All Implemented Interfaces:
Iterable<PriorityQueueNode.Double<E>>, Collection<PriorityQueueNode.Double<E>>, Queue<PriorityQueueNode.Double<E>>, MergeablePriorityQueueDouble<E,BinaryHeapDouble<E>>, PriorityQueueDouble<E>, Copyable<BinaryHeapDouble<E>>
public final class BinaryHeapDouble<E> extends Object implements MergeablePriorityQueueDouble<E,BinaryHeapDouble<E>>, Copyable<BinaryHeapDouble<E>>

An implementation of a Binary Heap. An instance of a BinaryHeapDouble contains (element, priority) pairs, such that the elements are distinct. The priority values are of type double.

Priority order: BinaryHeapDouble instances are created via factory methods with names beginning with create. The priority order depends upon the factory method used to create the BinaryHeapDouble. Methods named createMinHeap produce a min heap with priority order minimum-priority-first-out. Methods named createMaxHeap produce a max heap with priority order maximum-priority-first-out.

Distinctness: The Object.hashCode() and Object.equals(java.lang.Object) methods are used to enforce distinctness, so be sure that the class of the elements properly implements these methods, or else behavior is not guaranteed.

Creating instances: To create an instance, use one of the factory methods, such as with:


 BinaryHeapDouble<String> pq = BinaryHeapDouble.createMinHeap();

Method runtimes: The asymptotic runtime of the methods of this class are as follows (where n is the current size of the heap and m is the size of a Collection parameter where relevant):

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static final int
    DEFAULT_INITIAL_CAPACITY
    The default initial capacity.

  • Method Summary

    Modifier and Type
    Method
    Description
    final boolean
    addAll(Collection<? extends PriorityQueueNode.Double<E>> c)
    Adds all (element, priority) pairs from a Collection to the PriorityQueueDouble, provided the elements are not already in the PriorityQueueDouble.
    final boolean
    change(E element, double priority)
    Changes the priority of an element if the element is present in the PriorityQueueDouble, and otherwise adds the (element, priority) pair to the PriorityQueueDouble.
    final void
    clear()
    Clears the PriorityQueueDouble, removing all elements.
    final boolean
    contains(Object o)
    Checks if this PriorityQueueDouble contains a given element or an (element, priority) pair with a given element.
    BinaryHeapDouble<E>
    copy()
    Creates an identical copy of this object.
    static <E> BinaryHeapDouble<E>
    createMaxHeap()
    Creates an empty BinaryHeapDouble with the DEFAULT_INITIAL_CAPACITY as the initial capacity, and a maximum-priority-first-out priority order.
    static <E> BinaryHeapDouble<E>
    createMaxHeap(int initialCapacity)
    Creates an empty BinaryHeapDouble with a specified initial capacity, and a maximum-priority-first-out priority order.
    static <E> BinaryHeapDouble<E>
    createMaxHeap(Collection<PriorityQueueNode.Double<E>> initialElements)
    Creates a BinaryHeapDouble from a collection of (element, priority) pairs, with a maximum-priority-first-out priority order.
    static <E> BinaryHeapDouble<E>
    createMinHeap()
    Creates an empty BinaryHeapDouble with the DEFAULT_INITIAL_CAPACITY as the initial capacity, and a minimum-priority-first-out priority order.
    static <E> BinaryHeapDouble<E>
    createMinHeap(int initialCapacity)
    Creates an empty BinaryHeapDouble with a specified initial capacity, and a minimum-priority-first-out priority order.
    static <E> BinaryHeapDouble<E>
    createMinHeap(Collection<PriorityQueueNode.Double<E>> initialElements)
    Creates a BinaryHeapDouble from a collection of (element, priority) pairs, with a minimum-priority-first-out priority order.
    final boolean
    demote(E element, double priority)
    Demotes an element relative to priority order if the element is present in the PriorityQueueDouble.
    final void
    ensureCapacity(int minCapacity)
    Increases the capacity if the capacity is not already at least the specified minimum.
    boolean
    equals(Object other)
    Checks if this BinaryHeapDouble contains the same (element, priority) pairs as another BinaryHeapDouble, including the specific order within the BinaryHeapDouble, as well as that the priority order is the same.
    int
    hashCode()
    Computes a hashCode for the BinaryHeapDouble.
    final boolean
    isEmpty()
    Checks if the PriorityQueueDouble is empty.
    final Iterator<PriorityQueueNode.Double<E>>
    iterator()
    Returns an iterator over the (element, priority) pairs in a mostly arbitrary order (i.e., you must not assume any particular order).
    boolean
    merge(BinaryHeapDouble<E> other)
    Merges another priority queue into this one, adding all of its (element, priority) pairs.
    final boolean
    offer(E element, double priority)
    Adds an (element, priority) pair to the PriorityQueueDouble with a specified priority, provided the element is not already in the PriorityQueueDouble.
    final boolean
    offer(PriorityQueueNode.Double<E> pair)
    Adds an (element, priority) pair to the PriorityQueueDouble, provided the element is not already in the PriorityQueueDouble.
    final PriorityQueueNode.Double<E>
    peek()
    Gets the next (element, priority) pair in priority order from this PriorityQueueDouble, without removing it.
    final E
    peekElement()
    Gets the next element in priority order from this PriorityQueueDouble, without removing it.
    final double
    peekPriority()
    Gets the priority of the next element in priority order in the PriorityQueueDouble.
    final double
    peekPriority(E element)
    Gets the priority of a specified element if it is present in the PriorityQueueDouble.
    final PriorityQueueNode.Double<E>
    poll()
    Removes and returns the next (element, priority) pair in priority order from this PriorityQueueDouble.
    final E
    pollElement()
    Removes and returns the next element in priority order from this PriorityQueueDouble.
    final boolean
    promote(E element, double priority)
    Promotes an element relative to priority order if the element is present in the PriorityQueueDouble.
    final boolean
    remove(Object o)
    Removes from this PriorityQueueDouble the (element, priority) pair, if present, for a specified element or element from a specified (element, priority) pair.
    final boolean
    removeAll(Collection<?> c)
    Removes from this PriorityQueueDouble all (element, priority) pairs such that a given Collection c either contains the element or contains an (element, priority) pair with the same element.
    final boolean
    retainAll(Collection<?> c)
    Removes from this PriorityQueueDouble all (element, priority) pairs except for the elements or (element, priority) pairs contained in a given Collection c.
    final int
    size()
    Gets the current size of the PriorityQueueDouble, which is the number of (element, value) pairs that it contains.
    final Object[]
    toArray()
    Returns an array containing all of the (element, priority) pairs contained in the PriorityQueueDouble.
    final <T> T[]
    toArray(T[] array)
    Returns an array containing all of the (element, priority) pairs contained in the PriorityQueueDouble.
    final void
    trimToSize()
    Decreases the capacity to the current size of the BinaryHeapDouble, provided size is at least 1, and otherwise decreases capacity to 1.

    Methods inherited from class java.lang.Object

    clone, finalize, getClass, notify, notifyAll, toString, wait, wait, wait

    Methods inherited from interface java.util.Collection

    parallelStream, removeIf, spliterator, stream, toArray

    Methods inherited from interface java.lang.Iterable

    forEach

    Methods inherited from interface org.cicirello.ds.PriorityQueueDouble

    add, add, containsAll, element, remove, removeElement

  • Field Details

    • DEFAULT_INITIAL_CAPACITY

      public static final int DEFAULT_INITIAL_CAPACITY
      The default initial capacity.
      See Also:

  • Method Details

    • copy

      public BinaryHeapDouble<E> copy()
      Description copied from interface: Copyable
      Creates an identical copy of this object.
      Specified by:
      copy in interface Copyable<E>
      Returns:
      an identical copy of this object.

    • createMinHeap

      public static <E> BinaryHeapDouble<E> createMinHeap()
      Creates an empty BinaryHeapDouble with the DEFAULT_INITIAL_CAPACITY as the initial capacity, and a minimum-priority-first-out priority order.
      Type Parameters:
      E - The type of elements contained in the BinaryHeapDouble.
      Returns:
      an empty BinaryHeapDouble with a minimum-priority-first-out priority order

    • createMinHeap

      public static <E> BinaryHeapDouble<E> createMinHeap(int initialCapacity)
      Creates an empty BinaryHeapDouble with a specified initial capacity, and a minimum-priority-first-out priority order.
      Type Parameters:
      E - The type of elements contained in the BinaryHeapDouble.
      Parameters:
      initialCapacity - The initial capacity, which must be positive.
      Returns:
      an empty BinaryHeapDouble with a minimum-priority-first-out priority order
      Throws:
      IllegalArgumentException - if initialCapacity is less than or equal to 0.

    • createMinHeap

      public static <E> BinaryHeapDouble<E> createMinHeap(Collection<PriorityQueueNode.Double<E>> initialElements)
      Creates a BinaryHeapDouble from a collection of (element, priority) pairs, with a minimum-priority-first-out priority order.
      Type Parameters:
      E - The type of elements contained in the BinaryHeapDouble.
      Parameters:
      initialElements - The initial collection of (element, priority) pairs, which must be non-empty.
      Returns:
      a BinaryHeapDouble with a minimum-priority-first-out priority order
      Throws:
      IllegalArgumentException - if initialElements is empty, or if more than one pair in initialElements contains the same element.

    • createMaxHeap

      public static <E> BinaryHeapDouble<E> createMaxHeap()
      Creates an empty BinaryHeapDouble with the DEFAULT_INITIAL_CAPACITY as the initial capacity, and a maximum-priority-first-out priority order.
      Type Parameters:
      E - The type of elements contained in the BinaryHeapDouble.
      Returns:
      an empty BinaryHeapDouble with a maximum-priority-first-out priority order

    • createMaxHeap

      public static <E> BinaryHeapDouble<E> createMaxHeap(int initialCapacity)
      Creates an empty BinaryHeapDouble with a specified initial capacity, and a maximum-priority-first-out priority order.
      Type Parameters:
      E - The type of elements contained in the BinaryHeapDouble.
      Parameters:
      initialCapacity - The initial capacity, which must be positive.
      Returns:
      an empty BinaryHeapDouble with a maximum-priority-first-out priority order
      Throws:
      IllegalArgumentException - if initialCapacity is less than or equal to 0.

    • createMaxHeap

      public static <E> BinaryHeapDouble<E> createMaxHeap(Collection<PriorityQueueNode.Double<E>> initialElements)
      Creates a BinaryHeapDouble from a collection of (element, priority) pairs, with a maximum-priority-first-out priority order.
      Type Parameters:
      E - The type of elements contained in the BinaryHeapDouble.
      Parameters:
      initialElements - The initial collection of (element, priority) pairs, which must be non-empty.
      Returns:
      a BinaryHeapDouble with a maximum-priority-first-out priority order
      Throws:
      IllegalArgumentException - if initialElements is empty, or if more than one pair in initialElements contains the same element.

    • addAll

      public final boolean addAll(Collection<? extends PriorityQueueNode.Double<E>> c)
      Adds all (element, priority) pairs from a Collection to the PriorityQueueDouble, provided the elements are not already in the PriorityQueueDouble. The default implementation calls the PriorityQueueDouble.add(PriorityQueueNode.Double) for each pair in the Collection.

      The runtime of this method is O(n + m) where n is current size of the heap and m is the size of the Collection c. In general this is more efficient than calling add repeatedly, unless you are adding a relatively small number of elements, in which case you should instead call either offer(PriorityQueueNode.Double) or PriorityQueueDouble.add(PriorityQueueNode.Double) for each (element, priority) pair you want to add.

      Specified by:
      addAll in interface Collection<E>
      Specified by:
      addAll in interface PriorityQueueDouble<E>
      Parameters:
      c - the Collection of (element, priority) pairs to add.
      Returns:
      true if the (element, priority) pairs were added.
      Throws:
      IllegalArgumentException - if the heap already contains any of the (element, priority) pairs.

    • change

      public final boolean change(E element, double priority)
      Description copied from interface: PriorityQueueDouble
      Changes the priority of an element if the element is present in the PriorityQueueDouble, and otherwise adds the (element, priority) pair to the PriorityQueueDouble.
      Specified by:
      change in interface PriorityQueueDouble<E>
      Parameters:
      element - The element whose priority is to change.
      priority - Its new priority.
      Returns:
      true if and only if the PriorityQueueDouble changed as a consequence of this method call.

    • clear

      public final void clear()
      Description copied from interface: PriorityQueueDouble
      Clears the PriorityQueueDouble, removing all elements.
      Specified by:
      clear in interface Collection<E>
      Specified by:
      clear in interface PriorityQueueDouble<E>

    • contains

      public final boolean contains(Object o)
      Description copied from interface: PriorityQueueDouble
      Checks if this PriorityQueueDouble contains a given element or an (element, priority) pair with a given element.
      Specified by:
      contains in interface Collection<E>
      Specified by:
      contains in interface PriorityQueueDouble<E>
      Parameters:
      o - An element or (element, priority) pair to check for containment of the element.
      Returns:
      true if and only if this PriorityQueueDouble contains the element.

    • demote

      public final boolean demote(E element, double priority)
      Description copied from interface: PriorityQueueDouble
      Demotes an element relative to priority order if the element is present in the PriorityQueueDouble. For a min-heap, demotion means increasing the element's priority, while for a max-heap, demotion means decreasing its priority. If the element is not in the PriorityQueueDouble, or if its new priority is not a demotion, then this method does nothing.
      Specified by:
      demote in interface PriorityQueueDouble<E>
      Parameters:
      element - The element whose priority is to change.
      priority - Its new priority.
      Returns:
      true if and only if the PriorityQueueDouble changed as a consequence of this method call.

    • ensureCapacity

      public final void ensureCapacity(int minCapacity)
      Increases the capacity if the capacity is not already at least the specified minimum. If the capacity is at or above the requested minimum, then this method does nothing.
      Parameters:
      minCapacity - The desired minimum capacity.

    • equals

      public boolean equals(Object other)
      Checks if this BinaryHeapDouble contains the same (element, priority) pairs as another BinaryHeapDouble, including the specific order within the BinaryHeapDouble, as well as that the priority order is the same.
      Specified by:
      equals in interface Collection<E>
      Overrides:
      equals in class Object
      Parameters:
      other - The other BinaryHeapDouble.
      Returns:
      true if and only if this and other contain the same (element, priority) pairs, with the same priority order.

    • hashCode

      public int hashCode()
      Computes a hashCode for the BinaryHeapDouble.
      Specified by:
      hashCode in interface Collection<E>
      Overrides:
      hashCode in class Object
      Returns:
      a hashCode

    • isEmpty

      public final boolean isEmpty()
      Description copied from interface: PriorityQueueDouble
      Checks if the PriorityQueueDouble is empty.
      Specified by:
      isEmpty in interface Collection<E>
      Specified by:
      isEmpty in interface PriorityQueueDouble<E>
      Returns:
      true if and only if it is empty

    • iterator

      public final Iterator<PriorityQueueNode.Double<E>> iterator()
      Description copied from interface: PriorityQueueDouble
      Returns an iterator over the (element, priority) pairs in a mostly arbitrary order (i.e., you must not assume any particular order).
      Specified by:
      iterator in interface Collection<E>
      Specified by:
      iterator in interface Iterable<E>
      Specified by:
      iterator in interface PriorityQueueDouble<E>
      Returns:
      an iterator over the (element, priority) pairs

    • merge

      public boolean merge(BinaryHeapDouble<E> other)

      Merges another priority queue into this one, adding all of its (element, priority) pairs. This is a destructive operation with no guarantees to the state of the other priority queue upon completion. Additionally, implementations of this method may assume that other and this do not share any elements, and the priority queue may become unstable if they do. The priority order of both priority queues must be the same (e.g., both minheaps or both maxheaps).

      Specified by:
      merge in interface MergeablePriorityQueueDouble<E,BinaryHeapDouble<E>>
      Parameters:
      other - The priority queue that you want to merge into this. Implementations need not make any guarantees as to the state of other upon completion.
      Returns:
      true if and only if this priority queue changed as a result of the merge
      Throws:
      IllegalArgumentException - if this and other have different priority-order (e.g., one is a minheap while the other is a maxheap)

    • offer

      public final boolean offer(E element, double priority)
      Description copied from interface: PriorityQueueDouble
      Adds an (element, priority) pair to the PriorityQueueDouble with a specified priority, provided the element is not already in the PriorityQueueDouble.
      Specified by:
      offer in interface PriorityQueueDouble<E>
      Parameters:
      element - The element.
      priority - The priority of the element.
      Returns:
      true if the (element, priority) pair was added, and false if the PriorityQueueDouble already contained the element.

    • offer

      public final boolean offer(PriorityQueueNode.Double<E> pair)
      Description copied from interface: PriorityQueueDouble
      Adds an (element, priority) pair to the PriorityQueueDouble, provided the element is not already in the PriorityQueueDouble.
      Specified by:
      offer in interface PriorityQueueDouble<E>
      Specified by:
      offer in interface Queue<E>
      Parameters:
      pair - The (element, priority) pair to add.
      Returns:
      true if the (element, priority) pair was added, and false if the PriorityQueueDouble already contained the element.

    • peekElement

      public final E peekElement()
      Description copied from interface: PriorityQueueDouble
      Gets the next element in priority order from this PriorityQueueDouble, without removing it.
      Specified by:
      peekElement in interface PriorityQueueDouble<E>
      Returns:
      the next element in priority order, or null if empty.

    • peek

      public final PriorityQueueNode.Double<E> peek()
      Description copied from interface: PriorityQueueDouble
      Gets the next (element, priority) pair in priority order from this PriorityQueueDouble, without removing it.
      Specified by:
      peek in interface PriorityQueueDouble<E>
      Specified by:
      peek in interface Queue<E>
      Returns:
      the next (element, priority) pair in priority order, or null if empty.

    • peekPriority

      public final double peekPriority()
      Description copied from interface: PriorityQueueDouble
      Gets the priority of the next element in priority order in the PriorityQueueDouble.
      Specified by:
      peekPriority in interface PriorityQueueDouble<E>
      Returns:
      the priority of the next element in priority order.

    • peekPriority

      public final double peekPriority(E element)
      Description copied from interface: PriorityQueueDouble
      Gets the priority of a specified element if it is present in the PriorityQueueDouble. This interface does not define the behavior when the element is not present. Implementations may define the behavior when the element is not present.
      Specified by:
      peekPriority in interface PriorityQueueDouble<E>
      Parameters:
      element - The element whose priority is returned.
      Returns:
      the priority of a specified element.

    • pollElement

      public final E pollElement()
      Description copied from interface: PriorityQueueDouble
      Removes and returns the next element in priority order from this PriorityQueueDouble.
      Specified by:
      pollElement in interface PriorityQueueDouble<E>
      Returns:
      the next element in priority order, or null if empty.

    • poll

      public final PriorityQueueNode.Double<E> poll()
      Description copied from interface: PriorityQueueDouble
      Removes and returns the next (element, priority) pair in priority order from this PriorityQueueDouble.
      Specified by:
      poll in interface PriorityQueueDouble<E>
      Specified by:
      poll in interface Queue<E>
      Returns:
      the next (element, priority) pair in priority order, or null if empty.

    • promote

      public final boolean promote(E element, double priority)
      Description copied from interface: PriorityQueueDouble
      Promotes an element relative to priority order if the element is present in the PriorityQueueDouble. For a min-heap, promotion means decreasing the element's priority, while for a max-heap, promotion means increasing its priority. If the element is not in the PriorityQueueDouble, or if its new priority is not a promotion, then this method does nothing.
      Specified by:
      promote in interface PriorityQueueDouble<E>
      Parameters:
      element - The element whose priority is to change.
      priority - Its new priority.
      Returns:
      true if and only if the PriorityQueueDouble changed as a consequence of this method call.

    • remove

      public final boolean remove(Object o)
      Description copied from interface: PriorityQueueDouble
      Removes from this PriorityQueueDouble the (element, priority) pair, if present, for a specified element or element from a specified (element, priority) pair.
      Specified by:
      remove in interface Collection<E>
      Specified by:
      remove in interface PriorityQueueDouble<E>
      Parameters:
      o - An element or (element, priority) pair, such that element designates the desired pair to remove (note that if you pass an (element, priority) pair, only the element must match to cause removal.
      Returns:
      true if and only if an (element, priority) pair was removed as a result of this method call.

    • removeAll

      public final boolean removeAll(Collection<?> c)
      Removes from this PriorityQueueDouble all (element, priority) pairs such that a given Collection c either contains the element or contains an (element, priority) pair with the same element.

      The runtime of this method is O(n + m) where n is current size of the heap and m is the size of the Collection c. In general this is more efficient than calling remove repeatedly, unless you are removing a relatively small number of elements, in which case you should instead call remove(Object) for each element you want to remove.

      Specified by:
      removeAll in interface Collection<E>
      Specified by:
      removeAll in interface PriorityQueueDouble<E>
      Parameters:
      c - A Collection of elements or (element, priority) pairs for removal.
      Returns:
      true if and only if this PriorityQueueDouble changed as a result of this method.

    • retainAll

      public final boolean retainAll(Collection<?> c)
      Removes from this PriorityQueueDouble all (element, priority) pairs except for the elements or (element, priority) pairs contained in a given Collection c.

      The runtime of this method is O(n + m) where n is current size of the heap and m is the size of the Collection c. In general this is more efficient than calling remove repeatedly, unless you are removing a relatively small number of elements, in which case you should instead call remove(Object) for each element you want to remove.

      Specified by:
      retainAll in interface Collection<E>
      Specified by:
      retainAll in interface PriorityQueueDouble<E>
      Parameters:
      c - A Collection of elements or (element, priority) pairs to keep.
      Returns:
      true if and only if this PriorityQueueDouble changed as a result of this method.

    • size

      public final int size()
      Description copied from interface: PriorityQueueDouble
      Gets the current size of the PriorityQueueDouble, which is the number of (element, value) pairs that it contains.
      Specified by:
      size in interface Collection<E>
      Specified by:
      size in interface PriorityQueueDouble<E>
      Returns:
      the current size of the PriorityQueueDouble.

    • toArray

      public final Object[] toArray()
      Description copied from interface: PriorityQueueDouble
      Returns an array containing all of the (element, priority) pairs contained in the PriorityQueueDouble. The order is not guaranteed. The runtime component type is Object. The PriorityQueueDouble does not maintain any references to the array that is returned, instead creating a new array upon each call to the toArray method. The length of the array that is returned is equal to the current PriorityQueueDouble.size() of the PriorityQueueDouble.
      Specified by:
      toArray in interface Collection<E>
      Specified by:
      toArray in interface PriorityQueueDouble<E>
      Returns:
      an array, whose runtime component type is Object, containing all of the (element, priority) pairs currently in the PriorityQueueDouble.

    • toArray

      public final <T> T[] toArray(T[] array)
      Description copied from interface: PriorityQueueDouble
      Returns an array containing all of the (element, priority) pairs contained in the PriorityQueueDouble. The order is not guaranteed. The runtime component type is the same as the array passed to it as a parameter. If the specified array is large enough, then it is used, otherwise a new array is allocated whose length is equal to the current PriorityQueueDouble.size() of the PriorityQueueDouble. If the specified array is larger than the current size() of the PriorityQueueDouble, the first extra cell is set to null.
      Specified by:
      toArray in interface Collection<E>
      Specified by:
      toArray in interface PriorityQueueDouble<E>
      Type Parameters:
      T - The component type of the array to contain the (element, priority) pairs
      Parameters:
      array - The array in which to place the (element, priority) pairs, if it is sufficiently large, otherwise a new array of length PriorityQueueDouble.size() is allocated of the same runtime type as array.
      Returns:
      The array in which the (element, priority) pairs have been inserted.

    • trimToSize

      public final void trimToSize()
      Decreases the capacity to the current size of the BinaryHeapDouble, provided size is at least 1, and otherwise decreases capacity to 1. If the size and the capacity are the same, then this method does nothing.