net.cscott.jutil

Class FibonacciHeap<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.3 2004/01/13 21:40:19 cananian Exp $

Author: C. Scott Ananian

Constructor Summary
	FibonacciHeap() Creates a new, empty `FibonacciHeap`, sorted according to its keys' natural order.
	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`.
	FibonacciHeap(Collection<? extends Entry<? extends K,? extends V>> collection, Comparator<K> comparator) Constructs a new heap from a collection of `Map.Entry`s and a key comparator.

Method Summary
void	clear()
void	decreaseKey(Entry<K,V> me, K newkey)
void	delete(Entry<K,V> me)
Collection<Entry<K,V>>	entries()
Entry<K,V>	extractMinimum()
Entry<K,V>	insert(K key, V value) Insert an entry into the heap.
protected void	insert(Entry<K,V> me)
static void	main(String[] args) Self-test method.
Entry<K,V>	minimum()
protected K	setKey(Entry<K,V> me, K newkey)
int	size()
void	union(FibonacciHeap<K,V> h)
void	union(Heap<? extends K,? extends V> h)

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.