common
Class FibHeap

java.lang.Object
  extended by java.util.AbstractCollection
      extended by 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.