Class TrackedHeap<E extends TrackedHeap.Element>

java.lang.Object
de.tomatengames.util.data.TrackedHeap<E>
Type Parameters:
E - The type of the elements in the heap. Must extend TrackedHeap.Element.
public class TrackedHeap<E extends TrackedHeap.Element> extends Object
A heap that allows to efficiently update and remove arbitrary elements.

The first element is the smallest element according to the Comparator specified to the constructor.

This implementation is not thread-safe.

Since:
1.5

  • Constructor Details

    • TrackedHeap

      public TrackedHeap(@NotNull Comparator<E> comparator)
      Creates a new and empty TrackedHeap.
      Parameters:
      comparator - The comparator that will be used to compare elements. Not null. The smallest element is the first element.

  • Method Details

    • insert

      public boolean insert(@Nullable E element)
      Inserts the specified element into this heap. If the element is already in this heap, its position in the heap is updated using move(Element).
      Parameters:
      element - The element that should be inserted. If null, nothing happens.
      Returns:
      If the element has been inserted. If false, it was already in the heap and may have been moved.
      Throws:
      IllegalArgumentException - If the element is already in another heap.
      Implementation Note:
      O(log n)

    • remove

      public boolean remove(@Nullable E element)
      Removes the specified element from this heap. If the element is not in this heap, nothing happens.
      Parameters:
      element - The element that should be removed. If null, nothing happens.
      Returns:
      If the element has been removed successfully. If false, nothing happened.
      Implementation Note:
      O(log n)

    • getFirst

      public @Nullable E getFirst()
      Returns the first element of this heap. The first element is the smallest element according to the Comparator of the heap.
      Returns:
      The first element of this heap. If this heap is empty, null is returned.
      Implementation Note:
      O(1)

    • removeFirst

      public @Nullable E removeFirst()
      Returns and removes the first element of this heap. The first element is the smallest element according to the Comparator of the heap.
      Returns:
      The first element of this heap. If this heap is empty, null is returned and nothing happens.
      Implementation Note:
      O(log n)

    • move

      public void move(@Nullable E element)
      Moves the specified element to its position in the heap. This method should be called after the element changed its value considered by the Comparator in order to repair the heap.

      If the element is not present in this heap, nothing happens.

      This method should be preferred over the following semantically equivalent calls. 

      heap.increase(element);
heap.decrease(element);
      and 
      if (heap.remove(element)) {
    heap.insert(element);
}
      Parameters:
      element - The element that has been changed and should be moved. If null, nothing happens.
      Implementation Note:
      O(log n)

    • increase

      public void increase(@Nullable E element)
      Moves the specified element to its position in the heap if it increased. This method should be called after the element increased its value considered by the Comparator in order to repair the heap. Use move(Element) instead if the value may have decreased.

      If the element is not present in this heap, nothing happens. If the element decreased instead of increased, nothing happens.

      Parameters:
      element - The element that has been changed and should be moved. If null, nothing happens.
      See Also:
      Implementation Note:
      O(log n)

    • decrease

      public void decrease(@Nullable E element)
      Moves the specified element to its position in the heap if it decreased. This method should be called after the element decreased its value considered by the Comparator in order to repair the heap. Use move(Element) instead if the value may have increased.

      If the element is not present in this heap, nothing happens. If the element increased instead of decreased, nothing happens.

      Parameters:
      element - The element that has been changed and should be moved. If null, nothing happens.
      See Also:
      Implementation Note:
      O(log n)

    • clear

      public void clear()
      Removes all elements from this heap. The heap will be empty after this operation.
      Implementation Note:
      O(n)

    • isEmpty

      public boolean isEmpty()
      Returns if this heap is empty.
      Returns:
      If this heap is empty.

    • size

      public int size()
      Returns the number of elements in this heap.
      Returns:
      The number of elements in this heap. Not negative.

    • contains

      public boolean contains(@Nullable E element)
      Returns if this heap contains the specified element.
      Parameters:
      element - The element that should be checked. If null, false is returned.
      Returns:
      If this heap contains the specified element.
      Implementation Note:
      O(1)