Fibonacci Heap notes: a f-heap is a lazy binomial heap. so, we will have to have a few definitions for you to have more than mere words to go by, after you DRAW the definitions..just a thought. (these are not on the quiz. merely the final exam.) 1) Definition: Bk is a binomial tree of degree k, consisting of a root and subtrees B0, B1, B2, ...B(K-1) in order (either right to left or left to right), where each subscript less than k appears exactly once. (and, remember, binomial trees are general trees, NOT k-ary trees) 2) A binomial heap is a forest of binomial trees, where at most one of each B0, B1,...,B(k) appears in the forest, and the nodes in the binomial trees satisfy the partial order property associated with a min (max) heap: the value in a node is less than or equal to (greater than or equal to) the values in its child nodes. 3) A fibonacci heap is essentially a forest of binomial heaps, except that the fibonacci heap does not restrict the degrees of the binomial trees making up the forest. That is, an f-heap having k roots in the forest is not required to have exactly one of each of B0, B1, B2..B(K-1). An f-heap can have any number of Bi's present in any order, except after consolidation, when it can have at most 1 of a given Bi in the forest. However, not all Bi need to be represented. for example, suppose, prior to consolidation, an f-heap contains 3 B0's 1 B1 1 B2, and 2 B3 during consolidation, two of the 3 B0's are combined to produce a B1, giving 1 B0, 2 B1, 1 B2 and 2 B3 combining the 2 B1's gives 1 B0, 2 B2, and 2 B3 combining the 2 B2's gives 1 B0 and 3 B3 combining the 2 B3's gives 1 B0, 1 B3, and 1 B4 thus, the f-heap has no B1, or B2, and is not a binomial heap, but merely a forest of binomial trees, but only AFTER some operation that requires a consolidation step. 4) operations: find_min merely returns min value note: don't forget to include updating the min pointer in each of these operations except the find_min insert adds new element to forest (as a B0) union combines two heaps by adding new heap to forest consolidate in forest, combine binomial trees of like size until at most one BK for all K delete_min find min, remove min and union child BK's, consolidate, and find new min merge union and consolidate decrease_key NOT IMPLEMENTED THIS SEMESTER. remove_key NOT IMPLEMENTED THIS SEMESTER note: after decrease key or remove key, the f-heap will NO longer be a forest of binomial trees; however the rules for decrease and remove key are such that the desired depth limits are still met. 5) Yes, handle duplicate keys. when structures are used primarily for searching, we will make the "unique key" assumption, so as to avoid issues like bucketing (as discussed in lecture) however, heaps, in general, are not searched, but are used for computational or control purposes, where it is not always necessary, possible, or in fact, correct, to assume unique values. so, you need to accomodate the possiblity of duplicate entries in the fibonacci heap Technically, we have a map here, but i don't want to further confuse the issue. 6) The order of complexity of operations in a fibonacci heap i have abused the term "order of complexity is constant" slightly. unlike nearly all of the structures you have seen or programmed to date where you discuss the time complexity of a single operation, the behavior of a fibonacci heap is best analyzed assuming that a string of many operations is being performed we say that a method or operation is in AMORTIZED O(f(n)) if any sequence of m operations is in O(m f(n)) whenever m is greater than or equal to n, the number of nodes (or keys, or elements--whatever system system parameter is growing without bound) So, the minimim-finding operation in an F-heap is in Theta(1), since it always takes constant time to access the "min", regardless of the number of elements in the heap. Clearly any string of these operations would also be in amortized Theta(1). Since the insert operation attaches a new root into the forest and adjusting the "min", insert in an F-heap is in Theta(1). Since performing a union of two F-heaps is similar, it too, is in Theta(1). By, the same argument , any string of these operations: inserts, union, and find_min will be in amortized Theta(1). However, that's not the case for delete_min or merge, because just one of these operations can require examination of all root nodes in the forest. (note: the consolidate step serves to keep the number of roots 'small', relative to the size of the heap) Both of these will be in amortized O(log n).) It can be shown, although you are not responsible for doing so, that as long as you do enough manipulations of the heap, the rules governing the structure and the process are such that dividing the total amount of time taken for a large number of operations by the number of operations is constant with respect to n, the size of the heap. So, the short answer is: Any sequence of m operations on an f-heap that includes A merges and delete-mins and B unions, min-finding, and inserts takes time in O(B + A log(n)) as long as m is at least n. 7) If you choose to implement an F-heap for part 4, the relevant F-heap construction rules follow as an answer to the student question below. you would use this to replace the built-in java priority queue In the discussion above, you should have recognized that the choice of which two B0's and B3's to combine was arbitrary, which means that more than one valid f-tree can be constructed from a given data set. I hope this puts some of your questions to bed, and apologize for the length of the reply; however, i'd rather be wordy and complete than too concise ambiguous. you might want to check the reference of your choice on F-heaps. visit google. mmh MORE details follow: Question: A student writes: >Professor, > >Let's say we have heaps: heap1,heap2. > >When taking the union of two heaps, the spec says we're supposed to do it as an insert. Does this mean we are to loop through heap1's root level and insert those nodes one by one into heap2; or, are we supposed to add the root list of heap1 at the end/beginning of heap2 and then update the minimum? Thanks for your time, A student > Answer: But let me make it clearer. The fibonacci heap is described as needing several functions/methods insert, union, consolidate, merge, delete_min And, in fact this, too, is an artifact of folks not really understanding definitions. Why? INSERT: Because technically, a binomial heap consisting of one element defined as B0. Thus, the minimal (fewest nodes) fibonacci heap is a forest containing one B0, the binomial heap of degree 0. it will also have a min pointer, and a 'vector' or array where the entry in position k points to a Bk in the forest, or is empty if no Bk is present in the forest. For the sake of argument, suppose that the value in the node is 24. So, after the insert, the MIN is 24, and you have a forest consisting of a B0 having root value 24. Now, we INSERT 3. Well, technically, we are inserting a B0 having root value 3 into the forest. After we have added it to the forest, we have a forest consisting of two B0's, with the min pointing to the node containing 3. The mental trick here is to recognize that insert is really adding a binomial heap to the existing forest, by adding the root of that binomial heap to the structure containing the roots of the other binomial heap---and the actual degree of the binomial heap is irrelevant. UNION: So, one way to define the union of f-heap Z and with an existing f-heap W is to INSERT the root of each binomial heap in Z into the structure holding the roots of f-heap W, and adjust the MIN pointer. The object model might work better if we recognize that inserting a number into the f-heap is the same as UNION with a f-heap consisting of a B0 (!) In fact, this is similar to the concept of a wrapper that has to be used in JAVA with constants--they still need to be "objects" however, from a time perspective, it may be faster to treat the insert different that is, not as a union. CONSOLIDATE: this requires you to combine the binomial heaps of like degree in the fibonacci heap until at most one of each degree remains. this is done by using the array that points to a B0 if one exists, a B1 if one exists, and so on and modifying the vector appropriately after, say, two B1's are combined to produce a B2. If there were no remaining B1's after that, the entry associated with '1' would be set to null, and either the new B2 would be combined with the B2 pointed to by the '2' entry of the array or a null entry in that spot will be replaced by the pointer to the new B2. and so on. consolidation is over when at most one of any Bk is present in the forest. After consolidation, a delete min operation would be able to find the new min in time that was proportional to log n. Manipulating the f-heap now becomes: UNION as being a LOGICAL insertion of the binomial heaps making up one f-heap into the other. < finally, your answer> we did not specify how you should implement your INSERT or your UNION. the correct answer would be the faster or more space efficient way, as determined by your programming language's rules and your applications time/space tradeoff requirements. in English, if you were using a linked list implementation, you'd just attach the two lists to make a bigger circular queue or linked list however, in an object oriented language in which memory effects hidden from the user, it might be that it's better in the long run to insert each root into the new forest. i don't honestly know because i'm not a JAVA expert. for completeness: MERGE: use either combination of INSERT or UNION, as discussed above to produce a single forest, or f-heap then CONSOLIDATE and update min DELETE_MIN: remove node containing min value (which is by definition a root of a binomial heap), MERGE the subtrees of the root with the existing heap and then, CONSOLIDATE and update min in each case, make sure that the min is updated, and maintain the array of pointers to a Bk of each size present in the forest. this is why it's not quite right to think of them as independent methods :-) sorry for the length of the answer, but, i'm trying to get you to see the separation of the abstract f-heapness from the implementation-specific definitions. (and, no, i didn't expect you guys to come here understanding this..and it's not always clear to the casual observer :-) ) mmh ps as long as the rules explained for time complexity are followed, you can use an equivalent combination of 'better for JAVA than linked lists" stuff. oh, and, alexis said on the discussion board. at this stage of the game, you can adopt anyone's fibonacci pseudocode, as always. but, taking the code from a student in the class, or adapting someone's java source code for a fibonacci or binomial heap, with or without correct attribution, is prohibited at this time.