Fibonacci Heap

You will be implementing a min heap. This will be used for storing item objects, which have a name field and corresponding metric, which will be used as the key. I suggest that you use a min pointer which will always point to the min value on the top list of nodes. The total number of items could also be useful. You should also designate the head and tail of the top node list. This could be used in the print function to decide which node to call the function with. It is important to differentiate when you have printed each node once.

For insert, add the new element as a root in the forest of binary trees and update the MIN reference as needed. For delete min, remove the node with the minimum value, add its child subtrees to the root-level of the f-heap, update the MIN reference and then consolidate by combining binomial heaps of like degree until at most one of each degree is present at the root level. For union, add one heap to the root level of the other as in an insert, and update the MIN reference. For consolidate, combine binomial heaps at the root-level of like degree until at most one of each degree remain. For merge, take the union of the two heaps, update the MIN reference and then consolidate. As long as your f-heap satisfies the min-heap property; its component subtrees satisfy the structural requirements of binomial trees; and you have printed it out as described in the print heap section, you should receive full credit.

Although the linked-list implementation described in the fibonacci tree references is not efficient for a JAVA implementation, you are neither required to use it nor will you be penalized for not doing so.

Web Accessibility