A Fibonacci heap is a particular type of data structure (specifically, a type of heap) that consists of a collection of heap-ordered trees. Fibonacci heaps are a desirable way to store data if the number of "extract minimum" and "delete" operations are small and the number of "decrease value" operations are large.
A Fibonacci heap is basically a normal heap with only a few changes specifically to speed up the ability to decrease a certain key in a tree. A Fibonacci heap consists of a collection of heap-ordered trees, where a heap-ordered tree is a tree in which each child node is greater in value than its parent (and, alternately, each parent is lesser in value than its child). These trees are collected together in a doubly-linked list constructed in a circular fashion, so that there is no beginning nor end; traversing one way along the list will eventually bring you back to the start.
Let's take a look at a sample Fibonacci heap:
/----------->----------->----------->----------->-----------\
| |
\----(23)---<----(7)----<----(3)----<----(17)---<----(24)---/
/|\ | /\
/ | \ | / \
/-->---/--|--\-->--\ | /->--/-->-\--->--\
| / | \ | | | / \ |
\--(18)--(52)-(38)-/ (30) \-(26)--<--(46)--/
| | |
(39) (41) (35)
You can see that the basic heap is linked together by a circular linked list, and each set of children of these are linked together in a similar list. Also note that each child has a greater value than his or her parent. The reason for the particular ordering (and large number of root nodes) is that the nodes were added in an order such that whenever a new "minimum" node for the whole heap is added, it is added to the base of the heap itself and a new tree is started, with all future nodes with higher value being added only to that tree.
This tree is most effective when you have to reduce the value of a particular node, because it operates in O(1), or linear time on average; this is because a particular node, when its value is reduced in a Fibonacci heap, rarely is required to move when the heap covers a reasonable set of values. This tree is very slow, however, at deleting operations, because there is no efficient way to re-insert the children of the node other than one at a time.
Fibonacci heaps are good for solving mazes, simply because most of the operations in finding the best solution to a maze revolve around building a tree (comparable to similar data structures in speed) and then reducing the values in the tree when improved paths are found (faster than similar data structures). In essence, this data structure is very useful when attempting to solve minimum spanning tree problems and single-source shortest path problems.
However, most algorithms that use heaps for data storage require speedy extraction of specific pieces of data from that heap, and for that, the Fibonacci heap is a very poor choice, indeed.
In summary, Fibonacci trees are useful data structures for solving certain types of problems, but are quite poor at aiding in the solution of other problems.
Credit for development of the fibonacci heap goes to Ronald Rivest, Thomas Cormen, and Charles Leiserson.