org.apache.nutch.util
Class FibonacciHeap

java.lang.Object
  org.apache.nutch.util.FibonacciHeap

public class FibonacciHeap

extends Object

A Fibonacci Heap, as described in Introduction to Algorithms by Charles E. Leiserson, Thomas H. Cormen, Ronald L. Rivest.

A Fibonacci heap is a very efficient data structure for priority queuing.

Constructor Summary

FibonacciHeap()
Creates a new FibonacciHeap.

Method Summary

void	add(Object item, int priority) Adds the Object item, with the supplied priority.
boolean	contains(Object item) Returns true if item exists in this FibonacciHeap, false otherwise.
void	decreaseKey(Object item, int priority) Decreases the priority value associated with item.
Object	peekMin() Returns the same Object that popMin() would, without removing it.
Object	popMin() Returns the object which has the lowest priority in the heap.
int	size() Returns the number of objects in the heap.

Methods inherited from class java.lang.Object

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

Constructor Detail

FibonacciHeap

public FibonacciHeap()

Creates a new FibonacciHeap.

Method Detail

add

public void add(Object item,
                int priority)

Adds the Object item, with the supplied priority.

contains

public boolean contains(Object item)

Returns true if item exists in this FibonacciHeap, false otherwise.

peekMin

public Object peekMin()

Returns the same Object that popMin() would, without removing it.

size

public int size()

Returns the number of objects in the heap.

popMin

public Object popMin()

Returns the object which has the lowest priority in the heap. If the heap is empty, null is returned.

decreaseKey

public void decreaseKey(Object item,
                        int priority)

Decreases the priority value associated with item.

item must exist in the heap, and it's current priority must be greater than priority.

Throws:

IllegalStateException - if item does not exist in the heap, or if item already has an equal or lower priority than the suppliedpriority.