In [1]:

```
# %load ../../preconfig.py
%matplotlib inline
import matplotlib.pyplot as plt
import seaborn as sns
plt.rcParams['axes.grid'] = False
from __future__ import division
#import numpy as np
#import pandas as pd
#import itertools
import logging
logger = logging.getLogger()
```

dual purpose:

support a set of operations of 'mergeable heap'.

its several Fibonacci-heap operations run in constant amortized time.

In [2]:

```
plt.figure(figsize=(15,10))
plt.imshow(plt.imread('./res/fig19_1.png'))
```

Out[2]:

In theory:

Fibonacci heaps are especially desiable when the number of EXTRAC-MIN and DELETE operations is **small** relative to the number of other operations performed.

In practice:

Ordinary binary heaps are more preferred because of the constant factors and programing complexity of Fibonacci heaps.

A **Fibonacci heap** is a collection of rooted trees that are **min-heap ordered**(the key of a node is greater than or equal to the key of its parent).

In [3]:

```
plt.figure(figsize=(15,10))
plt.imshow(plt.imread('./res/fig19_2.png'))
```

Out[3]:

Links:

each node $x$ contains a pointer $x.p$ to its parent and a pointer $x.child$ to

**any one**of its children.**child list**of $x$: The children of $x$ are linked together in a**circular, doubly**linked list. Each child $y$ in a child list has pointers $y.left$ and $y.right$.

Why doubly linked lists?- Insert or remove diretcly.
- Concatenate easily.

Attributes:

For each node $x$:

- $x.degree$: the number of children in the child list of node $x$.
- $x.mark$: whether node $x$ has lost a child since the last time $x$ was made the child of another node. (DECRESE-KEY operation).

For heap $H$:

- $H.min$: root pointer.
- $H.n$: the number of nodes currently in $H$.

$$\phi (H) = t(H) + 2 m(H)$$ where $t(H)$ is the number of trees in the root list and $m(H)$ is the number of marked nodes.

An upper bound $D(n)$ on the maximum degree of any node in an $n$-node Fibonacci heap: $D(n) \leq \lfloor \lg n \rfloor$.

In [8]:

```
plt.figure()
plt.imshow(plt.imread('./res/fig19_3a.png'))
plt.figure()
plt.imshow(plt.imread('./res/fig19_3.png'))
```

Out[8]:

In [9]:

```
plt.imshow(plt.imread('./res/fig19_unit.png'))
```

Out[9]:

$O(\lg n)$

extracte the minimum node, and also consolidate trees in the root list finally occurs.

In [10]:

```
plt.imshow(plt.imread('./res/fig19_extract_min.png'))
```

Out[10]:

consolidating the root list consists of repeatedly excuting the following steps until every root in the root list has a distince degree values:

Find two roots $x$ and $y$ in the root list with the same degree. Let $x.key \leq y.key$.

Link $y$ to $x$: remove $y$ from the root list, and make $y$ a child of $x$ by calling the FIB-HEAP-LINK procedure.

In [21]:

```
plt.figure(figsize=(20,15))
plt.subplot(2,1,1)
plt.imshow(plt.imread('./res/fig19_4a.png'))
plt.subplot(2,1,2)
plt.imshow(plt.imread('./res/fig19_4b.png'))
```

Out[21]: