Some Notes about Fibonacci HeapsPermalink

Operations:Permalink

• make_heap Return an empty heap
• insert(i,h) Add item i to heap h.
• find_min(h) Return the smallest item in heap h
• delete_min(h) Delete min from heap h and return it
• meld(h1, h2) Return the heap formed by putting all elements in h1 with all the elements in h2. h1 and h2 are destroyed.
• decrease_key(delta, i, h) Assume that position of i is known. Decrease the value of item i of delta (delta > 0)
• delete(i, h) Assume that position of i is known. Delete i from heap

Amortized Time ComplexityPermalink

• delete_min(h) and delete(i, h) takes O(logn) time
• Other operations take O(1) time

StructurePermalink

• Heap Ordered Trees: Rooted tree containing a set of item, 1 item / node, with items arranged in heap order
• Heap Order: Key of item x is no less than the key of the item in its parent p(x), provided x has a parent.
• Linking: Combine two item-disjoint trees into one. (Make one root (bigger) a child of the other (smaller))
• Fibonacci heap (F-heap): Collection item disjoint heap ordered trees. (the algorithms impose an additinoal constraint).
• rank r(x): Number of children of node x. It turns out that if x has n descendants, the number of children is at most logn.
• Nodes will be marked or unmarked.

Representation of F-HeapPermalink

• Each node contains pointer to its parent (or to null if it doesn’t have one).
• Each node has a pointer to one of its children (or to null if it doesn’t have any).
• The children of each node are in a doubly linked circular list.
• Node has its rank r(x) and a bit indicating its mark.
• All the roots of the (sub)heaps are in a circular list.
• There is a pointer to a root containing an item of minimum key (minimum node of the F-heap).

DefinitionsPermalink

• S: Collection of Heaps.
• Φ(S): Potential of S.
• m operations with times t1,t2,⋯,tm
• ai amortized time for operation i.
• Φi: Potential after operation i.
• Φ0: Initial potential.
• ∑ti=∑(ai−Φi+Φi−1)=Φ0−Φm+∑ai
• Φ0 is initially zero.
• Φi is non-negative.

IdeaPermalink

• Potential of a collection of heaps: The total number of trees they contain.
• Initial potential is zero
• make_heap, find_min, insert, and meld take O(1) time.
• Insertion increases the number of trees by one. And other operations do not affect the number of trees
• delete_min: Amorzied time O(logn) where n is the number of items in the heap. Increases the number of trees by at most logn.
• Linking Step: Decreases the number of trees by one.

Implementation of OperationsPermalink

• make_heap Just retur null
• find_min(h) Return the minimum node of h
• insert(i, h) Create a heap of only node i and replace h by meld of h and the new heap
• meld(h1, h2) Combine the root lists of h1 and h2 into one list and set the minimum node to the appropriate new minimum node.

delete_min(h)Permalink

• Remove the minimum node (x) from h
• Concatenate the list of children of x with the list of roots of h (other than x)
• Repeat the following Linking Step until it no longer applies
  • Find any two trees whose roots have the same rank and link them (the new root has rank +1)
• Form a list of the remaining roots.
• Find the item of minimum key.

Note: Implementation (use an array indexed by ranks).

decrease_key(delta, i, h)Permalink

• Key of item i is decreased by delta
• Cut out the node x containing item i from its parent
• x and its descendants is added as a new tree of h.
• The appropriate update operations are performed

delete(i, h)Permalink

• Find node x containing item i.
• Cut out the node x containing item i from its parent.
• Form a new list of roots by concatenating the list of children of x with the original list of roots.
• The appropriate update operations are performed.
• delete takes O(1), except when the minimum element is deleted.

Additional Details (Cascade Cut)Permalink

• When node x has been made a child of another node by a linking step and it loses 2 of its children through cuts, we cut the edge joining x and its parent and we make x ad new root (as in decrease_key)
• A decrease_key or delete operation my casue a possibly large number of cascading cuts.

Marking NodesPermalink

• Purpose: Keep track of where to make cascade cuts.
• Unmark x: When making a root node x a child of another node in a linking step
• When curring edge joining x and its parent (p(x)), we decrease the rank of p(x) and check it p(x) is a root
  • if p(x) is not a root, we mark it if it is unmarked and cut the edge to its parent it it is marked. (latter cut my be cascading)
• Each cut takes O(1).

Crucial PropertiesPermalink

1. Each tree in an F-heap has a size at lease exponential in the rank of its root. i.e. the number of children is at most logn.
2. The number of cascading cutus that take place during a sequence of heap operations is bounded by the number of decrease key and delete operations.

ObservationsPermalink

• The purpose of cascade cuts in to preserve property 1.
• Loss of two children rule limits the frequency of cascade cuts.

Lemma 1: Let x be any node in a F-heap. Arrange the children of x in the order they were linked to x, from earliest to latest. Then the ith child of x has rank of at least i−2.

Corollary 1: A node of rank k in an F-heap has at least Fk+2≥ϕk descendants, including itself, where Fk is the kth Fibonacci number and ϕ is the golden ratio.

RedefinitionPermalink

• Potential: Total numbere of trees plus twice the number of marked nonroot nodes.
• The bounds of O(1) for make_heap, find_min, insert, and meld remain valid, as does not O(logn) bound for delete_min.
• delete_min(h): increases the potential by at most 1.4404logn minus the number of linking steps, since, if the minimum node has rank k, then ϕk≤n and thus

Revist decrease_keyPermalink

• Causes potential to increase by at most three mins the number of cascading cuts, since
  • the first cut converts a possible unmarked nonroot node into a root
  • each cascading cut converts a marked nonroot node into a root
  • the last cut can convert a nonroot node from unmarked to marked
• It follows that decrease key has an O(1) amortized time bound.

Revist deletePermalink

Just combine the analysis of decrease_key with delete_min

SummaryPermalink

If we begin with no F-heaps and perform an arbitrary sequence of F-heap operations, then the total time is at most the total amortized time, where the amortized time is O(logn) for each delete_min or delete, and O(1) for each other operations.