- Some Notes about Fibonacci Heaps

# 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

- 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$.
- 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.