 |  Introduction to Algorithms, 2/e Thomas H. Cormen,
Dartmouth College
Charles E. Leiserson,
Massachusetts Institute of Technology
Ronald L. Rivest,
Massachusetts Institute of Technology
Clifford Stein,
Columbia University
Fibonacci Heaps
Glossary
| consolidating | consolidating the root list reduces the number of trees in the Fibonacci heap. Consolidating the root list consists of repeatedly executing the following steps until every root in the root list has a distinct degree value.- Find two roots x and y in the root list with the same degree, where key[x] ≤ key[y].
- Link y to x: remove y from the root list, and make y a child of x. This operation is performed by the FIB-HEAP-LINK procedure. The field degree[x] is incremented, and the mark on y, if any, is cleared.
(See page 483)
| | | | | Fibonacci heap | a collection of min-heap-ordered trees. The trees in a Fibonacci heap are not constrained to be binomial trees. Unlike trees within binomial heaps, which are ordered, trees within Fibonacci heaps are rooted but unordered.
(See page 477)
| | | | | child list | In a Fibonacci heap, each node x contains a pointer p[x] to its parent and a pointer child[x] to any one of its children. The children of x are linked together in a circular, doubly linked list, which we call the child list of x. Each child y in a child list has pointers left[y] and right[y] that point to y's left and right siblings, respectively. If node y is an only child, then left[y] = right[y] = y. The order in which siblings appear in a child list is arbitrary.
(See page 477)
| | | | | link | Link y to x is one step in the process of consolidating the root list of a Fibonacci heap. To link y to x the process removes y from the root list, and makes y a child of x.
(See page 483)
| | | | | cutting | The CUT procedure "cuts" the link between x and its parent y, making x a root.
(See page 490)
| | | | | cascading-cut | x might be the second child cut from its parent y since the time that y was linked to another node. Therefore, the FIB-HEAP-DECREASE-KEY algorithm performs a cascading-cut operation on y. If y is a root, then the test in CASCADING-CUT causes the procedure to just return. If y is unmarked, the procedure marks it, since its first child has just been cut, and returns. If y is marked, however, it has just lost its second child; y is cut, and CASCADING-CUT calls itself recursively on y's parent z. The CASCADING-CUT procedure recurses its way up the tree until either a root or an unmarked node is found.
(See page 490)
|
|
2002 McGraw-Hill Higher Education