This page contains a Java Applet which
interactively demonstrates the composition and usage of a data structure
called a Fibonacci heap. A Fibonacci heap (F-heap)
is a collection of heap-ordered trees. F-heaps are the type of data
structure in which the work that must be done to reorder the structure is
postponed until the very last possible moment. F-heaps are useful for
algorithms involving graph data structures, such as those used for computing
shortest paths in computer networks. The classic text, Algorithms and
Data Structures, by Cormen et. al. contains an excellent discussion of
F-heaps. The common operations supported by
F-heaps are insert, minimum, extract-min, union, decrease-key, and delete.
All of these operations are available in the Applet and instructions for their execution
is contained below.
INSERT: Select insert
from the list of operations. Enter an integer key in the range [0, 99] into the text field. Press the
start button and a new node with the key value specified will be inserted into the heap.
EXTRACT-MIN: Select extract-min from the list of operations. Press the start button to begin the operation. Press the step button to incrementally step through the operation or the finish button to complete the operation in one step.
DECREASE-KEY:
Select decrease-key from the list of operations. Select a node in the
heap by clicking on it. Enter a new key in the text field which is less than
the key of the selected node. Press the start button to begin the operation.
Press the step button to incrementally step through the operation or the
finish button to complete the operation in one step.
DELETE: Select delete from the list of operations. Select a node in the heap by clicking on it. Press the start button to begin the operation. Press the step button to incrementally step through the operation or the finish button to complete the operation in one step.
General Notes:
The key values in this Applet were limited to the range [0, 99] for display purposes only. This limitation is in no way tied to the data structure itself.
Unmarked nodes are displayed in black. Marked nodes are displayed in red.
The clear button may be used to destroy the current heap at any time.
The load button may be used to load the heap from page 428 of the Cormen text (1st Ed.) at any time. Any other existing heaps will be destroyed.
All operations are begun with the start button. Operations may be completed by repeatedly pressing the step button to step through the operation or by pressing the finish button at any time to complete the operation.
This project was designed and created by James Welle in partial fulfillment of the summa cum laude degree requirements in the Institute of Technology at the University of Minnesota. All work was done during Spring Semester 2001 under the advisement of Dr. Ravi Janardan of the Department of Computer Science.
A more thorough discussion of Fibonacci heaps and this project is located here: Project Documentation