net.cscott.jutil
Class FibonacciHeap<K,V>

java.lang.Object
  net.cscott.jutil.AbstractHeap<K,V>
      net.cscott.jutil.FibonacciHeap<K,V>

All Implemented Interfaces:

Heap<K,V>

public class FibonacciHeap<K,V>
extends AbstractHeap<K,V>

A FibonacciHeap allows amortized O(1) time bounds for create, insert, minimum, union, and decrease-key operations, and amortized O(lg n) run times for extract-min and delete.

Implementation is based on the description in Introduction to Algorithms by Cormen, Leiserson, and Riverst, in Chapter 21.

Version:

$Id: FibonacciHeap.java,v 1.8 2006-10-30 19:58:05 cananian Exp $

Author:

C. Scott Ananian

Constructor Summary

FibonacciHeap()
Creates a new, empty FibonacciHeap, sorted according to its keys' natural order.

FibonacciHeap(Collection<? extends Map.Entry<? extends K,? extends V>> collection, Comparator<K> comparator)
Constructs a new heap from a collection of Map.Entrys and a key comparator.

FibonacciHeap(Comparator<K> c)
Creates a new, empty FibonacciHeap, sorted according to the given Comparator.

FibonacciHeap(Heap<K,? extends V> h)
Constructs a new heap with the same entries as the specified Heap.

Method Summary

void	clear() Removes all entries from this Heap.
void	decreaseKey(Map.Entry<K,V> me, K newkey) Replace the key in the specified map entry with the specified smaller key.
void	delete(Map.Entry<K,V> me) Remove the specified map entry from the mapping.
Collection<Map.Entry<K,V>>	entries() Returns a collection view of all the Map.Entrys in this Heap.
Map.Entry<K,V>	extractMinimum() Remove and return a map entry with minimal key.
Map.Entry<K,V>	insert(K key, V value) Insert an entry into the heap.
protected void	insert(Map.Entry<K,V> me) This method should insert the specified Map.Entry, which is not currently in the Heap, into the Heap.
static void	main(String[] args) Self-test method.
Map.Entry<K,V>	minimum() Returns a mapping entry with minimal key.
protected K	setKey(Map.Entry<K,V> me, K newkey) This method should set the key for the specified Map.Entry to the given newkey.
int	size() Returns the number of entries in this Heap.
void	union(FibonacciHeap<K,V> h)
void	union(Heap<? extends K,? extends V> h) Merges all of the mappings from the specified Heap into this Heap.

Methods inherited from class net.cscott.jutil.AbstractHeap

comparator, entryComparator, equals, hashCode, isEmpty, keyComparator, toString, updateKey

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

FibonacciHeap

public FibonacciHeap()

Creates a new, empty FibonacciHeap, sorted according to its keys' natural order. All keys inserted into the new map must implement the Comparable interface. O(1) time.

FibonacciHeap

public FibonacciHeap(Comparator<K> c)

Creates a new, empty FibonacciHeap, sorted according to the given Comparator. O(1) time.

FibonacciHeap

public FibonacciHeap(Heap<K,? extends V> h)

Constructs a new heap with the same entries as the specified Heap. O(n) time.

FibonacciHeap

public FibonacciHeap(Collection<? extends Map.Entry<? extends K,? extends V>> collection,
                     Comparator<K> comparator)

Constructs a new heap from a collection of Map.Entrys and a key comparator. O(n) time.

Method Detail

insert

public Map.Entry<K,V> insert(K key,
                             V value)

Insert an entry into the heap.

Specified by:

insert in interface Heap<K,V>

Specified by:

insert in class AbstractHeap<K,V>

insert

protected void insert(Map.Entry<K,V> me)

Description copied from class: AbstractHeap

This method should insert the specified Map.Entry, which is not currently in the Heap, into the Heap. Implementation is optional, but it is required if you use the default implementation of updateKey().

Overrides:

insert in class AbstractHeap<K,V>

minimum

public Map.Entry<K,V> minimum()

Description copied from interface: Heap

Returns a mapping entry with minimal key.

Specified by:

minimum in interface Heap<K,V>

Specified by:

minimum in class AbstractHeap<K,V>

union

public void union(FibonacciHeap<K,V> h)

union

public void union(Heap<? extends K,? extends V> h)

Description copied from interface: Heap

Merges all of the mappings from the specified Heap into this Heap. Note that duplicates are permitted. After calling union(), the Heap passed in as an argument will be empty.

Note that usually efficient implementations of this method require that the Heap argument be from the same implementation as this. (That is, they must both be binomial heaps, or both fibonacci heaps, etc.)

Specified by:

union in interface Heap<K,V>

Overrides:

union in class AbstractHeap<K,V>

extractMinimum

public Map.Entry<K,V> extractMinimum()

Description copied from interface: Heap

Remove and return a map entry with minimal key.

Specified by:

extractMinimum in interface Heap<K,V>

Overrides:

extractMinimum in class AbstractHeap<K,V>

decreaseKey

public void decreaseKey(Map.Entry<K,V> me,
                        K newkey)

Description copied from interface: Heap

Replace the key in the specified map entry with the specified smaller key.

Specified by:

decreaseKey in interface Heap<K,V>

Specified by:

decreaseKey in class AbstractHeap<K,V>

delete

public void delete(Map.Entry<K,V> me)

Description copied from interface: Heap

Remove the specified map entry from the mapping.

Specified by:

delete in interface Heap<K,V>

Specified by:

delete in class AbstractHeap<K,V>

size

public int size()

Description copied from interface: Heap

Returns the number of entries in this Heap.

Specified by:

size in interface Heap<K,V>

Specified by:

size in class AbstractHeap<K,V>

clear

public void clear()

Description copied from interface: Heap

Removes all entries from this Heap.

Specified by:

clear in interface Heap<K,V>

Specified by:

clear in class AbstractHeap<K,V>

entries

public Collection<Map.Entry<K,V>> entries()

Description copied from interface: Heap

Returns a collection view of all the Map.Entrys in this Heap.

Specified by:

entries in interface Heap<K,V>

Specified by:

entries in class AbstractHeap<K,V>

setKey

protected final K setKey(Map.Entry<K,V> me,
                         K newkey)

Description copied from class: AbstractHeap

This method should set the key for the specified Map.Entry to the given newkey. Implementation is optional, but it is required if you use the default implementation of updateKey().

Overrides:

setKey in class AbstractHeap<K,V>

main

public static void main(String[] args)

Self-test method.