📄 chap21.htm
字号:
<HTML><HEAD>
<TITLE>Intro to Algorithms: CHAPTER 21: FIBONACCI HEAPS</TITLE></HEAD><BODY BGCOLOR="#FFFFFF">
<a href="chap22.htm"><img align=right src="../../images/next.gif" alt="Next Chapter" border=0></A>
<a href="toc.htm"><img align=right src="../../images/toc.gif" alt="Return to Table of Contents" border=0></A>
<a href="chap20.htm"><img align=right src="../../images/prev.gif" alt="Previous Chapter" border=0></A>
<h1><a name="0874_1692">CHAPTER 21: FIBONACCI HEAPS<a name="0874_1692"></h1><P>
<a name="0874_168f"><a name="0874_1690"><a name="0874_1691">In Chapter 20, we saw how binomial heaps support in <I>O</I>(lg <I>n</I>) worst-case time the mergeable-heap operations <FONT FACE="Courier New" SIZE=2>INSERT</FONT>, <FONT FACE="Courier New" SIZE=2>MINIMUM</FONT>, <FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New" SIZE=2>MIN</FONT>, and <FONT FACE="Courier New" SIZE=2>UNION</FONT>, plus the operations <FONT FACE="Courier New" SIZE=2>DECREASE</FONT>-<FONT FACE="Courier New" SIZE=2>KEY</FONT> and <FONT FACE="Courier New" SIZE=2>DELETE</FONT>. In this chapter, we shall examine Fibonacci heaps, which support the same operations but have the advantage that operations that do not involve deleting an element run in <I>O</I>(1) amortized time.<P>
From a theoretical standpoint, Fibonacci heaps are especially desirable when the number of <FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New" SIZE=2>MIN</FONT> and <FONT FACE="Courier New" SIZE=2>DELETE</FONT> operations is small relative to the number of other operations performed. This situation arises in many applications. For example, some algorithms for graph problems may call <FONT FACE="Courier New" SIZE=2>DECREASE</FONT>-<FONT FACE="Courier New" SIZE=2>KEY</FONT> once per edge. For dense graphs, which have many edges, the <I>O</I>(1) amortized time of each call of <FONT FACE="Courier New" SIZE=2>DECREASE</FONT>-<FONT FACE="Courier New" SIZE=2>KEY</FONT> adds up to a big improvement over the<img src="../images/bound.gif">(lg <I>n</I>) worst-case time of binary or binomial heaps. The asymptotically fastest algorithms to date for problems such as computing minimum spanning trees (Chapter 24) and finding single-source shortest paths (Chapter 25) make essential use of Fibonacci heaps.<P>
From a practical point of view, however, the constant factors and programming comple<I>x</I>ity of Fibonacci heaps make them less desirable than ordinary binary (or <I>k</I>-ary) heaps for most applications. Thus, Fibonacci heaps are predominantly of theoretical interest. If a much simpler data structure with the same amortized time bounds as Fibonacci heaps were developed, it would be of great practical use as well.<P>
Like a binomial heap, a Fibonacci heap is a collection of trees. Fibonacci heaps, in fact, are loosely based on binomial heaps. If neither <FONT FACE="Courier New" SIZE=2>DECREASE</FONT>-<FONT FACE="Courier New" SIZE=2>KEY</FONT> nor <FONT FACE="Courier New" SIZE=2>DELETE</FONT> is ever invoked on a Fibonacci heap, each tree in the heap is like a binomial tree. Fibonacci heaps differ from binomial heaps, however, in that they have a more rela<I>x</I>ed structure, allowing for improved asymptotic time bounds. Work that maintains the structure can be delayed until it is convenient to perform.<P>
Like the dynamic tables of Section 18.4, Fibonacci heaps offer a good example of a data structure designed with amortized analysis in mind. The intuition and analyses of Fibonacci heap operations in the remainder of this chapter rely heavily on the potential method of Section 18.3.<P>
The exposition in this chapter assumes that you have read Chapter 20 on binomial heaps. The specifications for the operations appear in that chapter, as does the table in Figure 20.1, which summarizes the time bounds for operations on binary heaps, binomial heaps, and Fibonacci heaps. Our presentation of the structure of Fibonacci heaps relies on that of binomial heap structure. You will also find that some of the operations performed on Fibonacci heaps are similar to those performed on binomial heaps.<P>
Like binomial heaps, Fibonacci heaps are not designed to give efficient support to the operation <FONT FACE="Courier New" SIZE=2>SEARCH</FONT>; operations that refer to a given node therefore require a pointer to that node as part of their input.<P>
Section 21.1 defines Fibonacci heaps, discusses their representation, and presents the potential function used for their amortized analysis. Section 21.2 shows how to implement the mergeable-heap operations and achieve the amortized time bounds shown in Figure 20.1. The remaining two operations, <FONT FACE="Courier New" SIZE=2>DECREASE</FONT>-<FONT FACE="Courier New" SIZE=2>KEY</FONT> and <FONT FACE="Courier New" SIZE=2>DELETE</FONT>, are presented in Section 21.3. Finally, Section 21.4 finishes off a key part of the analysis.<P>
<h1><a name="0876_1696">21.1 Structure of Fibonacci heaps<a name="0876_1696"></h1><P>
Like a binomial heap, a <I><B>Fibonacci heap</I></B> is a collection of heap-ordered trees. The trees in a Fibonacci heap are not constrained to be binomial trees, however. Figure 21.1 (a) shows an example of a Fibonacci heap.<P>
<a name="0876_1692">Unlike trees within binomial heaps, which are ordered, trees within Fibonacci heaps are rooted but unordered. As Figure 21.1(b) shows, each node <I>x</I> contains a pointer <I>p</I>[<I>x</I>] to its parent and a pointer <I>child</I>[<I>x</I>] to any one of its children. The children of <I>x</I> are linked together in a circular, doubly linked list , which we call the <I><B>child list</I></B><I> </I>of <I>x</I>. Each child <I>y</I> in a child list has pointers <I>left</I>[<I>y</I>] and <I>right</I>[<I>y</I>] that point to <I>y</I>'s left and right siblings, respectively. If node <I>y</I> is an only child, then <I>left</I>[<I>y</I>] = <I>right</I>[<I>y</I>] = <I>y</I>. The order in which siblings appear in a child list is arbitrary.<P>
Circular, doubly linked lists (see Section 11.2) have two advantages for use in Fibonacci heaps. First, we can remove a node from a circular, doubly linked list in <I>O</I>(1) time. Second, given two such lists, we can concatenate them (or "splice" them together) into one circular, doubly linked list in <I>O</I>(1) time. In the descriptions of Fibonacci heap operations, we shall refer to these operations informally, letting the reader fill in the details of their implementations.<P>
<a name="0876_1693">Two other fields in each node will be of use. The number of children in the child list of node <I>x</I> is stored in <I>degree</I>[<I>x</I>]. The boolean-valued field <I>mark</I>[<I>x</I>] indicates whether node <I>x h</I>as lost a child since the last time <I>x</I> was made the child of another node. We won't worry about the details of marking nodes until Section 21.3. Newly created nodes are unmarked, and a node <I>x</I> becomes unmarked whenever it is made the child of another node.<P>
<img src="422_a.gif"><P>
<h4><a name="0876_1697">Figure 21.1 (a) A Fibonacci heap consisting of five heap-ordered trees and 14 nodes. The dashed line indicates the root list. The minimum node of the heap is the node containing the key 3. The three marked nodes are blackened. The potential of this particular Fibonacci heap is 5 + 2 <img src="../images/dot10.gif"> 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 the remaining figures in this chapter, since all the information shown here can be determined from what appears in part (a).<a name="0876_1697"></sub></sup></h4><P>
<a name="0876_1694">A given Fibonacci heap <I>H</I> is accessed by a pointer <I>min</I>[<I>H</I>] to the root of the tree containing a minimum key; this node is called the <I><B>minimum node</I></B> of the Fibonacci heap. If a Fibonacci heap <I>H</I> his empty, then <I>min</I>[<I>H</I>] = <FONT FACE="Courier New" SIZE=2>NIL</FONT>.<P>
<a name="0876_1695">The roots of all the trees in a Fibonacci heap are linked together using their <I>left</I> and <I>right</I> pointers into a circular, doubly linked list called the <I><B>root</I></B><I> <B>list</I></B> of the Fibonacci heap. The pointer <I>min</I>[<I>H</I>] thus points to the node in the root list whose key is minimum. The order of the trees within a root list is arbitrary.<P>
We rely on one other attribute for a Fibonacci heap <I>H</I>: the number of nodes currently in <I>H</I> is kept in <I>n</I>[<I>H</I>].<P>
<h2>Potential function</h2><P>
<a name="0877_1696"><a name="0877_1697"><a name="0877_1698">As mentioned, we shall use the potential method of Section 18.3 to analyze the performance of Fibonacci heap operations. For a given Fibonacci heap <I>H</I>, we indicate by <I>t</I>(<I>H</I>) the number of trees in the root list of <I>H</I> and by <I>m </I>(<I>H</I>) the number of marked nodes in <I>H</I>. The potential of Fibonacci heap <I>H</I> is then defined by<P>
<pre><img src="../images/phicap12.gif">(<I>H</I>) = <I>t</I>(<I>H</I>) + 2<I>m</I>(<I>H</I>) .</sub></sup></pre><P>
<h4><a name="0877_1699">(21.1)<a name="0877_1699"></sub></sup></h4><P>
For example, the potential of the Fibonacci heap shown in Figure 21.1 is 5 + 2 <img src="../images/dot10.gif"> 3 = 11. The potential of a set of Fibonacci heaps is the sum of the potentials of its constituent Fibonacci heaps. We shall assume that a unit of potential can pay for a constant amount of work, where the constant is sufficiently large to cover the cost of any of the specific constant-time pieces of work that we might encounter.<P>
We assume that a Fibonacci heap application begins with no heaps. The initial potential, therefore, is 0, and by equation (21.1), the potential is nonnegative at all subsequent times. From equation (18.2), an upper bound on the total amortized cost is thus an upper bound on the total actual cost for the sequence of operations.<P>
<P>
<h2>Maximum degree</h2><P>
<a name="0878_1699"><a name="0878_169a"><a name="0878_169b">The amortized analyses we shall perform in the remaining sections of this chapter assume that there is a known upper bound <I>D</I>(<I>n</I>) on the maximum degree of any code in an <I>n-</I>node Fibonacci heap. Exercise 21.2-3 shows that when only the mergeable-heap operations are supported, <I>D</I>(<I>n</I>) = <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"></FONT>lg <I>n</I><FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdr12.gif"><I>.</I></FONT> In Section 21.3, we shall show that when we support <FONT FACE="Courier New" SIZE=2>DECREASE</FONT>-<FONT FACE="Courier New" SIZE=2>KEY</FONT> and <FONT FACE="Courier New" SIZE=2>DELETE</FONT> as well, <I>D</I>(<I>n</I>) = <I>O</I>(lg <I>n</I>).<P>
<P>
<P>
<h1><a name="0879_169f">21.2 Mergeable-heap operations<a name="0879_169f"></h1><P>
<a name="0879_169c"><a name="0879_169d"><a name="0879_169e">In this section, we describe and analyze the mergeable-heap operations as implemented for Fibonacci heaps. If only these operations--<FONT FACE="Courier New" SIZE=2>MAKE</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT>, <FONT FACE="Courier New" SIZE=2>INSERT</FONT>, <FONT FACE="Courier New" SIZE=2>MINIMUM</FONT>, <FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New" SIZE=2>MIN</FONT>, and <FONT FACE="Courier New" SIZE=2>UNION</FONT>--are to be supported, each Fibonacci heap is simply a collection of "unordered" binomial trees. An <I><B>unordered binomial tree</I></B><I> </I>is like a binomial tree, and it, too, is defined recursively. The unordered binomial tree <I>U</I><SUB>0</SUB> consists of a single node, and an unordered binomial tree <I>U<SUB>k</I></SUB> consists of two unordered binomial trees <I>U<SUB>k</I>-1</SUB> for which the root of one is made into <I>any</I> child of the root of the other. Lemma 20.1, which gives properties of binomial trees, holds for unordered binomial trees as well, but with the following variation on property 4 (see Exercise 21.2-2):<P>
4' For the unordered binomial tree <I>U<SUB>k</I></SUB>.The root has degree <I>k</I>, which is greater than that of any other node. The children of the root are roots of subtrees <I>U<SUB>0</I></SUB>, <I>U</I><SUB>1</SUB>, . . . , <I>U<SUB>k-</I>1</SUB> in some order.<P>
Thus, if an <I>n</I>-node Fibonacci in heap is a collection of unordered binomial trees, then <I>D</I>(<I>n</I>) = lg <I>n</I>.<P>
The key idea in the mergeable-heap operations on Fibonacci heaps is to delay work as long as possible. There is a performance trade-off among implementations of the various operations. If the number of trees in a Fibonacci heap is small, then we can quickly determine the new minimum node during an <FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New" SIZE=2>MIN</FONT> operation. However, as we saw with binomial heaps in Exercise 20.2-10, we pay a price for ensuring that the number of trees is small: it can take up to <img src="../images/omega12.gif">(1g <I>n</I>) time to insert a node into a binomial heap or to unite two binomial heaps. As we shall see, we do not attempt to consolidate trees in a Fibonacci heap when we insert a new node or unite two heaps. We save the consolidation for the <FONT FACE="Courier New" SIZE=2>EXTRACT</FONT>-<FONT FACE="Courier New" SIZE=2>MIN</FONT> operation, which is when we really need to find the new minimum node.<P>
<h2>Creating a new Fibonacci heap</h2><P>
<a name="087a_169f">To make an empty Fibonacci heap, the <FONT FACE="Courier New" SIZE=2>MAKE</FONT>-<FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT> procedure allocates and returns the Fibonacci heap object <I>H</I>, where <I>n</I>[<I>H</I>] = 0 and <I>min</I>[<I>H</I>] = NIL; there are no trees in <I>H.</I> Because <I>t </I>(<I>H</I>) = 0 and <I>m</I>(<I>H</I>) = 0, the potential of the empty Fibonacci heap is <img src="../images/phicap12.gif">(<I>H</I>) = 0. The amortized cost of <FONT FACE="Courier New" SIZE=2>MAKE</FONT>-<FONT FACE="Courier New" SIZE=2>FIB</FONT>-<FONT FACE="Courier New" SIZE=2>HEAP</FONT> is thus equal to its <I>O</I>(1) actual cost.<P>
<P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -