Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 92
Текст из файла (страница 92)
Do you need to change the representation of a binomial heap? Do you need to addoperations beyond the mergeable-heap operations given in Figure 19.1? Give the running timeof your implementation.Chapter notesBinomial heaps were introduced in 1978 by Vuillemin [307]. Brown [49, 50] studied theirproperties in detail.Chapter 20: Fibonacci HeapsOverviewIn Chapter 19, we saw how binomial heaps support in O(lg n) worst-case time the mergeableheap operations INSERT, MINIMUM, EXTRACT-MIN, and UNION, plus the operationsDECREASE-KEY and DELETE. In this chapter, we shall examine Fibonacci heaps, whichsupport the same operations but have the advantage that operations that do not involvedeleting an element run in O(1) amortized time.From a theoretical standpoint, Fibonacci heaps are especially desirable when the number ofEXTRACT-MIN and DELETE operations is small relative to the number of other operationsperformed.
This situation arises in many applications. For example, some algorithms forgraph problems may call DECREASE-KEY once per edge. For dense graphs, which havemany edges, the O(1) amortized time of each call of DECREASE-KEY adds up to a bigimprovement over the Θ(lg n) worst-case time of binary or binomial heaps. Fast algorithmsfor problems such as computing minimum spanning trees (Chapter 23) and finding singlesource shortest paths (Chapter 24) make essential use of Fibonacci heaps.From a practical point of view, however, the constant factors and programming complexity ofFibonacci heaps make them less desirable than ordinary binary (or k-ary) heaps for mostapplications.
Thus, Fibonacci heaps are predominantly of theoretical interest. If a muchsimpler data structure with the same amortized time bounds as Fibonacci heaps weredeveloped, it would be of practical use as well.Like a binomial heap, a Fibonacci heap is a collection of trees. Fibonacci heaps, in fact, areloosely based on binomial heaps. If neither DECREASE-KEY nor DELETE is ever invokedon a Fibonacci heap, each tree in the heap is like a binomial tree.
Fibonacci heaps have a morerelaxed structure than binomial heaps, however, allowing for improved asymptotic timebounds. Work that maintains the structure can be delayed until it is convenient to perform.Like the dynamic tables of Section 17.4, Fibonacci heaps offer a good example of a datastructure designed with amortized analysis in mind. The intuition and analyses of Fibonacciheap operations in the remainder of this chapter rely heavily on the potential method ofSection 17.3.The exposition in this chapter assumes that you have read Chapter 19 on binomial heaps. Thespecifications for the operations appear in that chapter, as does the table in Figure 19.1, whichsummarizes the time bounds for operations on binary heaps, binomial heaps, and Fibonacciheaps.
Our presentation of the structure of Fibonacci heaps relies on that of binomial-heapstructure, and some of the operations performed on Fibonacci heaps are similar to thoseperformed on binomial heaps.Like binomial heaps, Fibonacci heaps are not designed to give efficient support to theoperation SEARCH; operations that refer to a given node therefore require a pointer to thatnode as part of their input.
When we use a Fibonacci heap in an application, we often store ahandle to the corresponding application object in each Fibonacci-heap element, as well as ahandle to corresponding Fibonacci-heap element in each application object.Section 20.1 defines Fibonacci heaps, discusses their representation, and presents the potentialfunction used for their amortized analysis. Section 20.2 shows how to implement themergeable-heap operations and achieve the amortized time bounds shown in Figure 19.1. Theremaining two operations, DECREASE-KEY and DELETE, are presented in Section 20.3.Finally, Section 20.4 finishes off a key part of the analysis and also explains the curious nameof the data structure.20.1 Structure of Fibonacci heapsLike a binomial heap, a Fibonacci heap is a collection of min-heap-ordered trees. The trees ina Fibonacci heap are not constrained to be binomial trees, however.
Figure 20.1(a) shows anexample of a Fibonacci heap.Figure 20.1: (a) A Fibonacci heap consisting of five min-heap-ordered trees and 14 nodes.The dashed line indicates the root list. The minimum node of the heap is the node containingthe key 3. The three marked nodes are blackened. The potential of this particular Fibonacciheap is 5+2·3 = 11. (b) A more complete representation showing pointers p (up arrows), child(down arrows), and left and right (sideways arrows). These details are omitted in theremaining figures in this chapter, since all the information shown here can be determinedfrom what appears in part (a).Unlike trees within binomial heaps, which are ordered, trees within Fibonacci heaps arerooted but unordered.
As Figure 20.1(b) shows, each node x contains a pointer p[x] to itsparent and a pointer child[x] to any one of its children. The children of x are linked together ina circular, doubly linked list, which we call the child list of x. Each child y in a child list haspointers left[y] and right[y] that point to y's left and right siblings, respectively. If node y is anonly child, then left[y] = right[y] = y. The order in which siblings appear in a child list isarbitrary.Circular, doubly linked lists (see Section 10.2) have two advantages for use in Fibonacciheaps. First, we can remove a node from a circular, doubly linked list in O(1) time.
Second,given two such lists, we can concatenate them (or "splice" them together) into one circular,doubly linked list in O(1) time. In the descriptions of Fibonacci heap operations, we shallrefer to these operations informally, letting the reader fill in the details of theirimplementations.Two other fields in each node will be of use. The number of children in the child list of node xis stored in degree[x].
The boolean-valued field mark[x] indicates whether node x has lost achild since the last time x was made the child of another node. Newly created nodes areunmarked, and a node x becomes unmarked whenever it is made the child of another node.Until we look at the DECREASE-KEY operation in Section 20.3, we will just set all markfields to FALSE.A given Fibonacci heap H is accessed by a pointer min[H] to the root of a tree containing aminimum key; this node is called the minimum node of the Fibonacci heap.
If a Fibonacciheap H is empty, then min[H] = NIL.The roots of all the trees in a Fibonacci heap are linked together using their left and rightpointers into a circular, doubly linked list called the root list of the Fibonacci heap. Thepointer min[H] thus points to the node in the root list whose key is minimum. The order of thetrees within a root list is arbitrary.We rely on one other attribute for a Fibonacci heap H: the number of nodes currently in H iskept in n[H].Potential functionAs mentioned, we shall use the potential method of Section 17.3 to analyze the performanceof Fibonacci heap operations.
For a given Fibonacci heap H, we indicate by t(H) the numberof trees in the root list of H and by m(H) the number of marked nodes in H. The potential ofFibonacci heap H is then defined by(20.1)(We will gain some intuition for this potential function in Section 20.3.) For example, thepotential of the Fibonacci heap shown in Figure 20.1 is 5 + 2·3 = 11. The potential of a set ofFibonacci heaps is the sum of the potentials of its constituent Fibonacci heaps. We shallassume that a unit of potential can pay for a constant amount of work, where the constant issufficiently large to cover the cost of any of the specific constant-time pieces of work that wemight encounter.We assume that a Fibonacci heap application begins with no heaps. The initial potential,therefore, is 0, and by equation (20.1), the potential is nonnegative at all subsequent times.From equation (17.3), an upper bound on the total amortized cost is thus an upper bound onthe total actual cost for the sequence of operations.Maximum degreeThe amortized analyses we shall perform in the remaining sections of this chapter assume thatthere is a known upper bound D(n) on the maximum degree of any node in an n-nodeFibonacci heap.
Exercise 20.2-3 shows that when only the mergeable-heap operations aresupported, D(n) ≤ ⌊lg n⌋. In Section 20.3, we shall show that when we support DECREASEKEY and DELETE as well, D(n) = O(lg n).20.2 Mergeable-heap operationsIn this section, we describe and analyze the mergeable-heap operations as implemented forFibonacci heaps. If only these operations-MAKE-HEAP, INSERT, MINIMUM, EXTRACTMIN, and UNION-are to be supported, each Fibonacci heap is simply a collection of"unordered" binomial trees.
An unordered binomial tree is like a binomial tree, and it, too, isdefined recursively. The unordered binomial tree U0 consists of a single node, and anunordered binomial tree Uk consists of two unordered binomial trees Uk-1 for which the root ofone is made into any child of the root of the other. Lemma 19.1, which gives properties ofbinomial trees, holds for unordered binomial trees as well, but with the following variation onproperty 4 (see Exercise 20.2-2):•4′. For the unordered binomial tree Uk, the root has degree k, which is greater than thatof any other node. The children of the root are roots of subtrees U0, U1, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
