Package zombie.core.utils
Class FibonacciHeap<T>
java.lang.Object
zombie.core.utils.FibonacciHeap<T>
-
Nested Class Summary
-
Constructor Summary
-
Method Summary
Modifier and TypeMethodDescriptionvoid
decreaseKey
(FibonacciHeap.Entry<T> entry, double newPriority) Decreases the key of the specified element to the new priority.void
delete
(int threadID, IsoGridSquare node) void
delete
(FibonacciHeap.Entry<T> entry) Deletes this Entry from the Fibonacci heap that contains it.Dequeues and returns the minimum element of the Fibonacci heap.void
empty()
Inserts the specified element into the Fibonacci heap with the specified priority.boolean
isEmpty()
Returns whether the heap is empty.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.min()
Returns an Entry object corresponding to the minimum element of the Fibonacci heap, throwing a NoSuchElementException if the heap is empty.int
size()
Returns the number of elements in the heap.
-
Constructor Details
-
FibonacciHeap
public FibonacciHeap()
-
-
Method Details
-
empty
public void empty() -
enqueue
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
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
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
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
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
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
-