Package zombie.core.utils

Class FibonacciHeap<T>

java.lang.Object
zombie.core.utils.FibonacciHeap<T>
public final class FibonacciHeap<T> extends Object

  • Constructor Details

    • FibonacciHeap

      public FibonacciHeap()

  • Method Details

    • empty

      public void empty()

    • enqueue

      public FibonacciHeap.Entry<T> enqueue(T value, double priority)
      Inserts the specified element into the Fibonacci heap with the specified priority. Its priority must be a valid double, so you cannot set the priority to NaN.
      Parameters:
      value - The value to insert.
      priority - Its priority, which must be valid.
      Returns:
      An Entry representing that element in the tree.

    • min

      public FibonacciHeap.Entry<T> min()
      Returns an Entry object corresponding to the minimum element of the Fibonacci heap, throwing a NoSuchElementException if the heap is empty.
      Returns:
      The smallest element of the heap.
      Throws:
      NoSuchElementException - If the heap is empty.

    • isEmpty

      public boolean isEmpty()
      Returns whether the heap is empty.
      Returns:
      Whether the heap is empty.

    • size

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

    • merge

      public static <T> FibonacciHeap<T> merge(FibonacciHeap<T> one, FibonacciHeap<T> two)
      Given two Fibonacci heaps, returns a new Fibonacci heap that contains all of the elements of the two heaps. Each of the input heaps is destructively modified by having all its elements removed. You can continue to use those heaps, but be aware that they will be empty after this call completes.
      Parameters:
      one - The first Fibonacci heap to merge.
      two - The second Fibonacci heap to merge.
      Returns:
      A new FibonacciHeap containing all of the elements of both heaps.

    • dequeueMin

      public FibonacciHeap.Entry<T> dequeueMin()
      Dequeues and returns the minimum element of the Fibonacci heap. If the heap is empty, this throws a NoSuchElementException.
      Returns:
      The smallest element of the Fibonacci heap.
      Throws:
      NoSuchElementException - If the heap is empty.

    • decreaseKey

      public void decreaseKey(FibonacciHeap.Entry<T> entry, double newPriority)
      Decreases the key of the specified element to the new priority. If the new priority is greater than the old priority, this function throws an IllegalArgumentException. The new priority must be a finite double, so you cannot set the priority to be NaN, or +/- infinity. Doing so also throws an IllegalArgumentException. It is assumed that the entry belongs in this heap. For efficiency reasons, this is not checked at runtime.
      Parameters:
      entry - The element whose priority should be decreased.
      newPriority - The new priority to associate with this entry.
      Throws:
      IllegalArgumentException - If the new priority exceeds the old priority, or if the argument is not a finite double.

    • delete

      public void delete(FibonacciHeap.Entry<T> entry)
      Deletes this Entry from the Fibonacci heap that contains it. It is assumed that the entry belongs in this heap. For efficiency reasons, this is not checked at runtime.
      Parameters:
      entry - The entry to delete.

    • delete

      public void delete(int threadID, IsoGridSquare node)