Package com.github.tommyettinger.ds

Class BinaryHeap<T extends BinaryHeap.Node>

java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractQueue<T>
com.github.tommyettinger.ds.BinaryHeap<T>
All Implemented Interfaces:
EnhancedCollection<T>, Iterable<T>, Collection<T>, Queue<T>
public class BinaryHeap<T extends BinaryHeap.Node> extends AbstractQueue<T> implements EnhancedCollection<T>
A binary heap that stores nodes which each have a float value and are sorted either lowest first or highest first. This can expand if its capacity is exceeded. It defaults to acting as a min-heap, sorting lowest-first. The BinaryHeap.Node class can be extended to store additional information.
This isn't a direct copy from libGDX, but it's very close. It implements Queue and Collection.

  • Field Details

  • Constructor Details

    • BinaryHeap

      public BinaryHeap()
      Constructs a BinaryHeap with 16 starting capacity, sorting lowest-first (a min-heap).

    • BinaryHeap

      public BinaryHeap(int capacity, boolean isMaxHeap)
      Constructs a BinaryHeap with the specified capacity and sorting order.
      Parameters:
      capacity - the initial capacity
      isMaxHeap - if true, this will sort highest-first; if false, it will sort lowest-first

    • BinaryHeap

      public BinaryHeap(Collection<? extends T> coll)
      Constructs a BinaryHeap with the contents from the given Collection of nodes, sorting lowest-first (a min-heap). If a duplicate node is present in coll, all repeats are ignored.
      Parameters:
      coll - a Collection of T (which must extend BinaryHeap.Node) or objects that subclass T

    • BinaryHeap

      public BinaryHeap(boolean isMaxHeap, Collection<? extends T> coll)
      Constructs a BinaryHeap with the specified sorting order and the contents from the given Collection of nodes. If a duplicate node is present in coll, all repeats are ignored.
      Parameters:
      isMaxHeap - if true, this will sort highest-first; if false, it will sort lowest-first
      coll - a Collection of T (which must extend BinaryHeap.Node) or objects that subclass T

    • BinaryHeap

      public BinaryHeap(T[] arr)
      Constructs a BinaryHeap with the contents from the given array of nodes, sorting lowest-first (a min-heap). If a duplicate node is present in arr, all repeats are ignored.
      Parameters:
      arr - an array of T (which must extend BinaryHeap.Node) or objects that subclass T

    • BinaryHeap

      public BinaryHeap(boolean isMaxHeap, T[] arr)
      Constructs a BinaryHeap with the specified sorting order and the contents from the given array of nodes. If a duplicate node is present in arr, all repeats are ignored.
      Parameters:
      isMaxHeap - if true, this will sort highest-first; if false, it will sort lowest-first
      arr - an array of T (which must extend BinaryHeap.Node) or objects that subclass T

  • Method Details

    • isMaxHeap

      public boolean isMaxHeap()
      Returns true if this is a max-heap (that is, it sorts highest-first), or false if this is a min-heap (it sorts lowest-first). If not specified, this is usually false; it can be set only in the constructor, such as BinaryHeap(int, boolean) or BinaryHeap(boolean, Collection).
      Returns:
      true if this sorts highest-first; false if it sorts lowest-first

    • addAll

      public boolean addAll(Collection<? extends T> c)
      Specified by:
      addAll in interface Collection<T extends BinaryHeap.Node>
      Overrides:
      addAll in class AbstractQueue<T extends BinaryHeap.Node>

    • addAll

      public boolean addAll(T[] c)
      Specified by:
      addAll in interface EnhancedCollection<T extends BinaryHeap.Node>

    • addAll

      public boolean addAll(T[] c, int offset, int length)
      Specified by:
      addAll in interface EnhancedCollection<T extends BinaryHeap.Node>

    • add

      public boolean add(T node)
      Adds the node to the heap using its current value. The node should not already be in the heap.
      Specified by:
      add in interface Collection<T extends BinaryHeap.Node>
      Specified by:
      add in interface Queue<T extends BinaryHeap.Node>
      Overrides:
      add in class AbstractQueue<T extends BinaryHeap.Node>

    • offer

      public boolean offer(T node)
      Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions. You can also use add(Node), but if you try to add a duplicate element with that, an IllegalStateException is thrown. Here, if you try to add a duplicate element, no Exception is thrown and this returns false.
      Specified by:
      offer in interface Queue<T extends BinaryHeap.Node>
      Parameters:
      node - the element to add; must not be null
      Returns:
      true if the element was added to this queue, else false (typically when node is already present in this BinaryHeap)
      Throws:
      ClassCastException - if the class of the specified element prevents it from being added to this queue
      NullPointerException - if the specified element is null

    • poll

      public T poll()
      Retrieves and removes the head of this queue, or returns null if this BinaryHeap is empty. The head is the item with the lowest value (or highest value if this heap is configured as a max heap).
      Specified by:
      poll in interface Queue<T extends BinaryHeap.Node>
      Returns:
      the head of this BinaryHeap, or null if this queue is empty
      Throws:
      ClassCastException - if the class of the specified element prevents it from being added to this queue

    • remove

      public T remove()
      Retrieves and removes the head of this queue. This method differs from poll() only in that it throws an exception if this queue is empty, and won't return null.
      Specified by:
      remove in interface Queue<T extends BinaryHeap.Node>
      Overrides:
      remove in class AbstractQueue<T extends BinaryHeap.Node>
      Returns:
      the head of this queue
      Throws:
      NoSuchElementException - if this queue is empty
      ClassCastException - if the class of the specified element prevents it from being added to this queue

    • add

      public boolean add(T node, float value)
      Sets the node's value and adds it to the heap. The node should not already be in the heap.

    • contains

      public boolean contains(Object node)
      Returns true if the heap contains the specified node. Exactly the same as contains(Object, boolean) with identity set to false.
      Specified by:
      contains in interface Collection<T extends BinaryHeap.Node>
      Overrides:
      contains in class AbstractCollection<T extends BinaryHeap.Node>
      Parameters:
      node - should be a T, which must extend BinaryHeap.Node; can be some other type, which gives false
      "Implementation Requirements"
      This implementation iterates over the elements in the collection, checking each element in turn for equality with the specified element via Object.equals(Object).

    • contains

      public boolean contains(Object node, boolean identity)
      Returns true if the heap contains the specified node.
      Parameters:
      node - should be a T, which must extend BinaryHeap.Node; can be some other type, which gives false
      identity - If true, == comparison will be used. If false, .equals() comparison will be used.

    • element

      public T element()
      Returns the first item in the heap. This is the item with the lowest value (or highest value if this heap is configured as a max heap). If the heap is empty, throws an NoSuchElementException.
      Specified by:
      element in interface Queue<T extends BinaryHeap.Node>
      Overrides:
      element in class AbstractQueue<T extends BinaryHeap.Node>
      Returns:
      the first item in the heap
      Throws:
      NoSuchElementException - if the heap is empty.
      ClassCastException - if the class of the specified element prevents it from being added to this queue

    • peek

      public T peek()
      Returns the first item in the heap. This is the item with the lowest value (or highest value if this heap is configured as a max heap). If the heap is empty, returns null.
      Specified by:
      peek in interface Queue<T extends BinaryHeap.Node>
      Returns:
      the first item in the heap, or null if the heap is empty
      Throws:
      ClassCastException - if the class of the specified element prevents it from being added to this queue

    • pop

      public T pop()
      Retrieves and removes the head of this queue, or returns null if this BinaryHeap is empty. The head is the item with the lowest value (or highest value if this heap is configured as a max heap).
      This method is identical to poll() in this class, but because poll() is defined as part of the Queue interface, whereas this method was defined ad-hoc by libGDX, poll() should be preferred in new code.
      Returns:
      the head of this BinaryHeap, or null if this queue is empty

    • remove

      public T remove(T node)
      Removes the given node and returns it. If the node is not present in this BinaryHeap or is invalid, this will probably throw an Exception.
      Parameters:
      node - a BinaryHeap.Node that should be present in this already
      Returns:
      node after its removal

    • size

      public int size()
      Specified by:
      size in interface Collection<T extends BinaryHeap.Node>
      Specified by:
      size in class AbstractCollection<T extends BinaryHeap.Node>

    • notEmpty

      public boolean notEmpty()
      Returns true if the heap has one or more items.

    • isEmpty

      public boolean isEmpty()
      Returns true if the heap is empty.
      Specified by:
      isEmpty in interface Collection<T extends BinaryHeap.Node>
      Overrides:
      isEmpty in class AbstractCollection<T extends BinaryHeap.Node>

    • clear

      public void clear()
      Removes all nodes from this BinaryHeap.
      Specified by:
      clear in interface Collection<T extends BinaryHeap.Node>
      Overrides:
      clear in class AbstractQueue<T extends BinaryHeap.Node>

    • setValue

      public void setValue(T node, float value)
      Changes the value of the node, which should already be in the heap.

    • remove

      public boolean remove(Object o)
      Specified by:
      remove in interface Collection<T extends BinaryHeap.Node>
      Overrides:
      remove in class AbstractCollection<T extends BinaryHeap.Node>

    • containsAll

      public boolean containsAll(Collection<?> c)
      Specified by:
      containsAll in interface Collection<T extends BinaryHeap.Node>
      Overrides:
      containsAll in class AbstractCollection<T extends BinaryHeap.Node>

    • containsAll

      public boolean containsAll(Object[] array)
      Exactly like containsAll(Collection), but takes an array instead of a Collection.
      Specified by:
      containsAll in interface EnhancedCollection<T extends BinaryHeap.Node>
      Parameters:
      array - array to be checked for containment in this set
      Returns:
      true if this set contains all the elements in the specified array
      See Also:

    • containsAll

      public boolean containsAll(Object[] array, int offset, int length)
      Like containsAll(Object[]), but only uses at most length items from array, starting at offset.
      Specified by:
      containsAll in interface EnhancedCollection<T extends BinaryHeap.Node>
      Parameters:
      array - array to be checked for containment in this set
      offset - the index of the first item in array to check
      length - how many items, at most, to check from array
      Returns:
      true if this set contains all the elements in the specified range of array
      See Also:

    • containsAnyIterable

      public boolean containsAnyIterable(Iterable<?> values)
      Returns true if this set contains any of the specified values.
      Specified by:
      containsAnyIterable in interface EnhancedCollection<T extends BinaryHeap.Node>
      Parameters:
      values - must not contain nulls, and must not be null itself
      Returns:
      true if this set contains any of the items in values, false otherwise

    • containsAny

      public boolean containsAny(Object[] values)
      Returns true if this set contains any of the specified values.
      Specified by:
      containsAny in interface EnhancedCollection<T extends BinaryHeap.Node>
      Parameters:
      values - must not contain nulls, and must not be null itself
      Returns:
      true if this set contains any of the items in values, false otherwise

    • containsAny

      public boolean containsAny(Object[] values, int offset, int length)
      Returns true if this set contains any items from the specified range of values.
      Specified by:
      containsAny in interface EnhancedCollection<T extends BinaryHeap.Node>
      Parameters:
      values - must not contain nulls, and must not be null itself
      offset - the index to start checking in values
      length - how many items to check from values
      Returns:
      true if this set contains any of the items in the given range of values, false otherwise

    • removeAll

      public boolean removeAll(Collection<?> other)
      Removes each object in other from this heap, removing an item once if it appears once, twice if it appears twice, and so on. In this respect, this acts like removeEachIterable(Iterable) rather than Collection's removeAll().
      Specified by:
      removeAll in interface Collection<T extends BinaryHeap.Node>
      Overrides:
      removeAll in class AbstractCollection<T extends BinaryHeap.Node>
      Parameters:
      other - collection containing elements to be removed from this collection
      Returns:
      true if any elements were removed, or false otherwise
      See Also:

    • removeAll

      public boolean removeAll(Object[] other)
      Exactly like removeAll(Collection), but takes an array instead of a Collection. This delegates entirely to removeEach(Object[]), and does not act like removeAll() does in other collections if there are duplicate nodes present in the heap.
      Specified by:
      removeAll in interface EnhancedCollection<T extends BinaryHeap.Node>
      Parameters:
      other - array containing elements to be removed from this list
      Returns:
      true if this list changed as a result of the call
      See Also:

    • removeAll

      public boolean removeAll(Object[] array, int offset, int length)
      Like removeAll(Object[]), but only uses at most length items from array, starting at offset. This delegates entirely to removeEach(Object[], int, int), and does not act like removeAll() does in other collections if there are duplicate nodes present in the heap.
      Specified by:
      removeAll in interface EnhancedCollection<T extends BinaryHeap.Node>
      Parameters:
      array - the elements to be removed from this list
      offset - the index of the first item in array to remove
      length - how many items, at most, to get from array and remove from this
      Returns:
      true if this list changed as a result of the call
      See Also:

    • removeEachIterable

      public boolean removeEachIterable(Iterable<?> other)
      Removes from this ObjectList element-wise occurrences of elements contained in the specified Iterable. Note that if a value is present more than once in this ObjectList, only one of those occurrences will be removed for each occurrence of that value in other. If other has the same contents as this ObjectList or has additional items, then removing each of other will clear this.
      Specified by:
      removeEachIterable in interface EnhancedCollection<T extends BinaryHeap.Node>
      Parameters:
      other - an Iterable of T items to remove one-by-one, such as another ObjectList or an ObjectSet
      Returns:
      true if this list was modified.

    • removeEach

      public boolean removeEach(Object[] array)
      Exactly like removeEachIterable(Iterable), but takes an array instead of a Collection.
      Specified by:
      removeEach in interface EnhancedCollection<T extends BinaryHeap.Node>
      Parameters:
      array - array containing elements to be removed from this list
      Returns:
      true if this list changed as a result of the call
      See Also:

    • removeEach

      public boolean removeEach(Object[] array, int offset, int length)
      Like removeEach(Object[]), but only uses at most length items from array, starting at offset.
      Specified by:
      removeEach in interface EnhancedCollection<T extends BinaryHeap.Node>
      Parameters:
      array - the elements to be removed from this list
      offset - the index of the first item in array to remove
      length - how many items, at most, to get from array and remove from this
      Returns:
      true if this list changed as a result of the call
      See Also:

    • equals

      public boolean equals(Object obj)
      Specified by:
      equals in interface Collection<T extends BinaryHeap.Node>
      Overrides:
      equals in class Object

    • hashCode

      public int hashCode()
      Specified by:
      hashCode in interface Collection<T extends BinaryHeap.Node>
      Overrides:
      hashCode in class Object

    • toString

      public String toString()
      Overrides:
      toString in class AbstractCollection<T extends BinaryHeap.Node>

    • iterator

      public BinaryHeap.HeapIterator<T> iterator()
      Returns an iterator over the elements contained in this collection.
      Specified by:
      iterator in interface Collection<T extends BinaryHeap.Node>
      Specified by:
      iterator in interface Iterable<T extends BinaryHeap.Node>
      Specified by:
      iterator in class AbstractCollection<T extends BinaryHeap.Node>
      Returns:
      an iterator over the elements contained in this collection

    • with

      @SafeVarargs public static <T extends BinaryHeap.Node> BinaryHeap<T> with(T... array)
      Builds a BinaryHeap with the min-heap property from the given array or varargs of items that extend BinaryHeap.Node. This is equivalent to minHeapWith(Node[]).
      Type Parameters:
      T - must extend BinaryHeap.Node
      Parameters:
      array - an array or varargs of items that extend BinaryHeap.Node
      Returns:
      a new BinaryHeap of T with the min-heap property.

    • minHeapWith

      @SafeVarargs public static <T extends BinaryHeap.Node> BinaryHeap<T> minHeapWith(T... array)
      Builds a BinaryHeap with the min-heap property from the given array or varargs of items that extend BinaryHeap.Node. This is equivalent to with(Node[]).
      Type Parameters:
      T - must extend BinaryHeap.Node
      Parameters:
      array - an array or varargs of items that extend BinaryHeap.Node
      Returns:
      a new BinaryHeap of T with the min-heap property.

    • maxHeapWith

      @SafeVarargs public static <T extends BinaryHeap.Node> BinaryHeap<T> maxHeapWith(T... array)
      Builds a BinaryHeap with the max-heap property from the given array or varargs of items that extend BinaryHeap.Node.
      Type Parameters:
      T - must extend BinaryHeap.Node
      Parameters:
      array - an array or varargs of items that extend BinaryHeap.Node
      Returns:
      a new BinaryHeap of T with the max-heap property.