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.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment