zombie.core.utils
Class FibonacciHeap<T>

java.lang.Object
  zombie.core.utils.FibonacciHeap<T>

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

A class representing a Fibonacci heap.

Author:

Keith Schwarz (htiek@cs.stanford.edu)

Nested Class Summary

static class

FibonacciHeap.Entry<T>

Constructor Summary

FibonacciHeap()

Method Summary

void	decreaseKey(FibonacciHeap.Entry<T> entry, double newPriority) Decreases the key of the specified element to the new priority.
void	delete(FibonacciHeap.Entry<T> entry) Deletes this Entry from the Fibonacci heap that contains it.
void	delete(int threadID, AStarPathMap.Node node)
FibonacciHeap.Entry<T>	dequeueMin() Dequeues and returns the minimum element of the Fibonacci heap.
void	empty()
FibonacciHeap.Entry<T>	enqueue(T value, double priority) 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.
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.
int	size() Returns the number of elements in the heap.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

FibonacciHeap

public FibonacciHeap()

Method Detail

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:

java.util.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:

java.util.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:

java.lang.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,
                   AStarPathMap.Node node)