Lecture Notes on Fibonacci Heaps

18.415/6.854 Advanced Algorithms September 3rd, 2008 Fibonacci heaps Lecturer: Michel X. Goemans 1 Introduction Today we will describe Fibonacci heaps, a data structure that provides a very efficient implementa tion of a priority queue. By priority quene we mesan a data structure that stores a set S of elements where with each elements we associate a key (s) being "priority" of that element. Now, we want the queue to handle three operations on set S: INSERT Adding a new element s' with a key k) to S EXTRACT-MIS Returning an element & of S having minimal key and removing s" from S DECREASE-KEY Replacing the value of a ley of some element a by a new, smaller value. The motivation behind the search for fast implementation of priority queues can be observed on the example of two classical graph problems: Single-source Shortest Paths and Minimum Spanning Tree. 1.1 Single-source Shortest Paths problem We are given a directed graph G (V. E), some vertex eV and a length function 1: E-Ron the arcs. Observe that we impose that the lengths are nonnegative. Now, for each vertex EV we want to compute the length d, (v) of the shortest path from s to e. The classical solution for this problem is Dijkstra's algorithm. The algorithm is 1. Maintain a priority queue containing some subset S of vertices of G with keys k(v). Initially, SV, k()=0 and k(v)+ 2. As long as S is nonempty. • Extract a vertex w from 5 with minimum key. Output (u) as the value of do(u). For each out-neighbor ∈ S of u, we update (ie, possibly decrease) the key k(e) of e to be min(k(v), k(u)+((u,v))). In this algorithm, k(v) represents the length of the shortest path from to v using only intermediate vertices not in S, and represents da(v) when extracted. The algorithm can be adapted to output the shortest paths. 1.2 Minimum Spanning Tree problem Given an undirected graph G (V. E) and a weight functione E R on edges, we would like a spanning tree of G of minimal weight. Surprisingly, one of the classical solutions of this problem - Prim's algorithm is very similar to the approach of Dijlestra's algorithm for Single-source Shortest Path problem. The algorithm is as follows: lect-1 1. Maintain a priority queue containing some subset S of vertices of G with keys k(e) and a tree T spanning VS. Initially, T0, SV, k(s)=0 for some arbitrary vertex and k(e) = +oc for 2. As long as S is nonempty: • Extract a vertex & from S with minimum key. If (first iteration), add to T the corresponding edge (ie. the minimum-weight edge connecting a to 7 of weight (u)). • For each neighbor vS of u, we update (ie, possibly decrease) k(v) to be min (k(), w((u, v)}}. 1.3 Number of priority queue operations We will not prove the correctness of the algorithms. However, for the sake of the running time analysis that we will do later, we notice that in both cases the algorithm uses V insert operations. [V] extract-min operations and, since each edge can enforce at most one decrease-key operation, at most El decrease-key operations. 2 Binary heaps The classical implementation of priority queues are binary heaps. A binary heap T is a binary tree whose nodes correspond to elements of the set. S and has two properties: • it is almost complete ie. If T has depth a then it has exactly 2 vertices on depth if i< h and the last level is filled from the left. heap-ordering: the key of every child is not smaller than the key of its parent. Keeping this properties in mind it is relatively easy (see [CLRS]) to develop procedures for inserting, extracting the minimal element and decreasing the key that exeente any of these operations in O(log n) time where a is the number of items in the priority queue. Therefore, since the number of elements is at most V in our applications, we obtain the total running time of both algorithms to be O((V+E) log] VI). Obviously, E 2 V in case of connected graphs and therefore the running time is dominated by the OE log |V) term corresponding to decrease-key operations. The question isc can we do better? 3 d-ary heaps One of the ideas to get a better running time is increasing the arity of the tree that we are using. If we use a d-ary tree instead of a binary one then we reduce the depth of our tree and thus our inserts and bottlenecking decrease-key operations execute in O(log (5) time. On the other hand, the execution of extract-min operation requires Old log, S]) time. So, by choosing the best possible d = [E]/[V]] we get the total running time of our algorithms to be O((E)+dVlog, VO(Elogτινη (V), which is a significant improvement for dense graphs. However, it turns out that we can do even better. Namely, we can implement priority queue in such a way that from the point of view of running time analysis of our algorithms the cost of DECREASE-KEY will be constant and costs of INSERT and EXTRACT-MIN will be logarithmic. This leads to the essentially optimal O(E+Vlog (VI) running time of both algorithms and for some present-day applicatione (think graphs with billions of edges) this improvement can make a huge difference. A comprehensive coverage of binary heaps (as well as Fibonacel heape) can be found in (CLRS). lect-2 4 Fibonacci heaps The Fibonacci heaps were proposed by Fredman and Tarjan in 1984 giving a very efficient imple mentation of the priority queues. The main motto of this construction is laziness - "we do work only when we must, and then use it to simplify the structure as much as possible so that the future work is casy". This way, we enforce that any sequence of operations has to contain a lot of cheap ones before we need to do something computationally expensive the formalization of this intuition will be given later. 4.1 Construction A Fibonacci hesap consists of a collection of heap-ordered trees (of variable arity) with following properties: 1. nodes of the trees corresponeal to elements being stored in the queue, 2. roots of heap-ordered trees are arranged in a doubly-linked list, 3. we keep a pointer to the root of a tree that corresponds to the element with minimum lary (note that heap-ordering of the trees implies that such minimum element has to be a root of some tree), 4. for each node we keep track of its rank (degree), Le, the number of its children, as well as whether it is marked (the purpose of marking will be defined later on). 5. size requirement: if a node a has rank & then the subtree rooted at a has at least F2 nodes, where is the i-th Fibonacci number, ie. Fo0, F₁1 and FFF For 122 We proceed now to describing how do we perform priority queue operation on our Fibonacci heap. 4.1.1 INSERT Inserting is very simple. We Just add the new elements as a new heap-ordered tree to our collection and check whether (s) is smaller that the current minimum for the quene if so then we change the pointer to the minimum accordingly (see Figure 1). 4.1.2 DECREASE-KEY When we decrease the key of an element s, if the heap-ordering is still satisfied then we do not need to do anything else. Otherwise, we just cut out of the tree in which it resides and put it as a root of a new tree in our collection (note that all the descendants of s are now in this new tree as well). We compare the new key of and the previously minimum læy and change the pointer accordingly (see Figure 1). This way we end up with something that looks like a desired Fibonacci heap. However, the problem with simply cutting each such a is that, when we perform in this manner many DECREASE KEY operations, we may end up violating the size requirement that we wanted to preserve. Therefore, to alleviate this issue we introduce an additional rule that when we cut & we check whether its parent is marked. If so then we cut the parent as well (and we unmark it). Otherwise, we just mark the parent. Note that we do this cutting recursively, so if the parent of marked parent of s is also marked then we cut it as well, and so on. Obviously, if we cut a root we are not doing anything, and so it is useless to mark a root. This (potentially cascading) cutting procedure therefore always ends. lect-3 Figure 1: Illustration of: (left side) inserting a new element to the Fibonacci hesap (right side) cutting a vertex in the first step of DECREASE-KEY operation. In both examples we assumed that the newly created root hus smaller key than the keys of all the other elements. 4.1.3 EXTRACT-MIN Finally, we can describe extracting the minimum element a". We start with removings" (recall that we stored the pointer to it) and putting all the children of s" as roots of new trees in our collection. Next, we scan the entire list of roots in our collection to find the new minimum element and we set the relevant pointer accordingly. In principle at this point we could be done, because we obtain once again a valid Fibonacci hesap. However, it is not hard to see that so far executing of any of our queue operations makes the list longer and longer. So, going through the whole list of roots during EXTRACT-MIN can be very expensive computationally. Therefore, in the spirit of laziness, if we have to do this work anyway then we can use this opportunity to do some cleaning as well, and avoid in this way the necessity of doing the whole work again when doing the next EXTRACT-MIN What we do is, as long as there are two trees whose roots have the same rank, say &, we merge these trees to obtain one tree of rank k+1. Merging consist of just comparing the keys of the roots and setting the root of the tree with larger key as a new child of the other root (see Figure 2). Note that since merging can introduce a second tree of rank + 1 in the collection, one root can take part in many merges. 4.2 Running-time Analysis Now we want to analyze the worst-case performance of the described Fibonacci heap data structure. 4.2.1 A worst-case example Let's imagine the following scenario: We do n consecutive INSERT operations into the Fibonacci heap such that it is a circular linked list containing all elements as singleton heaps. If we perform an EXTRACT-MIN operation on this Fibonacci heap, this operation will have to go through the entire list to determine the new minimum. This takes O(n) time an unbearable performance for just one operation. Ject-1 Figure 2: Illustration of merging of two trees of the same rank 4.2.2 Are Fibonacci heaps useless? Does this mean that Fibonacci heaps are inefficient No! Intuitively such heavy operations can occur only very rarely and make no big contribution to the overall running time of an algorithm using the heap. Being not able to give worst-case performance guarantees for each individual operation, we want to consider a sequence of operations and give a proof that, for any such sequence, the total ranning time is small, in the sense that this running time can be apportioned between the individual operations so that each has a small contribution. This type of analysis is called amortized analysis CLRS). More precisely, if we have different types of operations and we claim that the amortized running time of an operation of type jis at most ty, this means that for any sequence of operations composed of k, operations of type for all j1, (with operations of different types interlaced in any way), the total running time is upperbounded by 4.2.3 Excursion: Amortized Analysis via the Potential Method The most common way to perform amortized analysis is using the potential method. The idea of the potential method allows cheap operations to save up time for the use of heavy operations. This functions like a bank account with time deposited in it. The potential function & represents the balance in the account. Initially, the balance is zero, and remains nonnegative during the whole sequence. Now operations are performed having costs (Le running times) of ce, ca. C. Every operation is allowed to either pay more than its actual cost e, thereby increasing its amortized cost, placing the credit savings in the bank account thus increasing the balance 4, or pay less than the actual cost by withdrawing the difference from . This gives the amortized cost. Often one can think of the potential function as a measurement of the complexity of the data structure or configuration within an algorithm. In this case cheap operations are allowed to increase the internal complexity, while operations which simplify or clean up the data are allowed to take more time. Making this formal, a potential function, 4, maps a configuration D, of an evolving algorithm or data structure D into a nonnegative number. The start configuration is normalized to have the value : 4 = (Do) 0. Consider a sequence of operations 0,01,00 and let D, be the configuration of the data structure after performing the ith operation. We impose that the potential lect-5