common
Class FibHeap

java.lang.Object
  java.util.AbstractCollection
      common.FibHeap

All Implemented Interfaces:

Heap, java.lang.Iterable, java.util.Collection

public class FibHeap
extends java.util.AbstractCollection
implements Heap

A Fibonacci heap data structure, as described in Chapter 20 of Cormen, Leiserson, Rivest & Stein (2001).

Nested Class Summary

Nested classes/interfaces inherited from interface common.Heap

Heap.Entry

Constructor Summary

FibHeap()
Creates a new, empty Fibonnaci heap.

Method Summary

Heap.Entry	add(java.lang.Object o, double cost) Adds an entry to this heap for the given object and cost.
void	changeCost(Heap.Entry entry, double newCost) Throws an UnsupportedOperationException.
void	clear()
void	decreaseCost(Heap.Entry entry, double newCost) Decreases the cost for the given entry.
Heap.Entry	extractMin() Returns the minimum-cost entry in this heap and removes it from the heap.
boolean	isEmpty()
java.util.Iterator	iterator() Returns an iterator over the Heap.Entry objects in this heap.
static void	main(java.lang.String[] args) Test program.
Heap.Entry	peekMin() Returns the minimum-cost entry in this heap, without modifying the heap.
int	size()

Methods inherited from class java.util.AbstractCollection

add, addAll, contains, containsAll, remove, removeAll, retainAll, toArray, toArray, toString

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Collection

add, addAll, contains, containsAll, equals, hashCode, remove, removeAll, retainAll, toArray, toArray

Constructor Detail

FibHeap

public FibHeap()

Creates a new, empty Fibonnaci heap.

Method Detail

size

public int size()

Specified by:

size in interface java.util.Collection

Specified by:

size in class java.util.AbstractCollection

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface java.util.Collection

Overrides:

isEmpty in class java.util.AbstractCollection

clear

public void clear()

Specified by:

clear in interface java.util.Collection

Overrides:

clear in class java.util.AbstractCollection

iterator

public java.util.Iterator iterator()

Returns an iterator over the Heap.Entry objects in this heap. The iteration is not guaranteed to be in any particular order. The iterator does not support removal.

Specified by:

iterator in interface java.lang.Iterable

Specified by:

iterator in interface java.util.Collection

Specified by:

iterator in class java.util.AbstractCollection

peekMin

public Heap.Entry peekMin()

Description copied from interface: Heap

Returns the minimum-cost entry in this heap, without modifying the heap.

Specified by:

peekMin in interface Heap

extractMin

public Heap.Entry extractMin()

Description copied from interface: Heap

Returns the minimum-cost entry in this heap and removes it from the heap.

Specified by:

extractMin in interface Heap

add

public Heap.Entry add(java.lang.Object o,
                      double cost)

Description copied from interface: Heap

Adds an entry to this heap for the given object and cost. This does not affect any other entries for the same object. Returns the entry that was added.

Specified by:

add in interface Heap

decreaseCost

public void decreaseCost(Heap.Entry entry,
                         double newCost)

Decreases the cost for the given entry. The entry must already be in this heap, and the new cost must be less than or equal to its current cost.

Warning: If the new cost is greater than the current one, this method will not produce an error message, but the heap may behave incorrectly.

Specified by:

decreaseCost in interface Heap

changeCost

public void changeCost(Heap.Entry entry,
                       double newCost)

Throws an UnsupportedOperationException.

Specified by:

changeCost in interface Heap

main

public static void main(java.lang.String[] args)

Test program.