GaeBlogX Arista Networks, Software-Defined Networking

Fibonacci Heap

2017-06-09
Yanxi Chen

Some Notes about Fibonacci Heaps

Operations:

  • 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 $h_1$ with all the elements in $h_2$. $h_1$ and $h_2$ 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 Complexity

  • delete_min(h) and delete(i, h) takes $O(\log n)$ time
  • Other operations take $O(1)$ time

Structure

  • 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 $\log n$.
  • Nodes will be marked or unmarked.

Representation of F-Heap

  • 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).

Definitions

  • $S$: Collection of Heaps.
  • $\Phi(S)$: Potential of $S$.
  • $m$ operations with times $t_1,t_2,\cdots,t_m$
  • $a_i$ amortized time for operation $i$.
  • $\Phi_i$: Potential after operation $i$.
  • $\Phi_0$: Initial potential.
  • $\sum t_i=\sum(a_i-\Phi_i+\Phi_{i-1})=\Phi_0-\Phi_m+\sum a_i$
  • $\Phi_0$ is initially zero.
  • $\Phi_i$ is non-negative.

Idea

  • 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(\log n)$ where $n$ is the number of items in the heap. Increases the number of trees by at most $\log n$.
  • Linking Step: Decreases the number of trees by one.

Implementation of Operations

  • 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 $h_1$ and $h_2$ into one list and set the minimum node to the appropriate new minimum node.

delete_min(h)

  • 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)

  • 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)

  • 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)

  • 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 Nodes

  • 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 Properties

  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 $\log n$.
  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.

Observations

  • 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 $i^{th}$ child of $x$ has rank of at least $i-2$.

Corollary 1: A node of rank $k$ in an F-heap has at least $F_{k+2}\geq\phi^k$ descendants, including itself, where $F_k$ is the $k^{th}$ Fibonacci number and $\phi$ is the golden ratio.

Redefinition

  • 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(\log n)$ bound for delete_min.
  • delete_min(h): increases the potential by at most $1.4404\log n$ minus the number of linking steps, since, if the minimum node has rank $k$, then $\phi_k\leq n$ and thus

Revist decrease_key

  • 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 delete

Just combine the analysis of decrease_key with delete_min

Summary

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(\log n)$ for each delete_min or delete, and $O(1)$ for each other operations.


Comments

Search
Content