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.
<end answer>
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.