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()
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.
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?
Attributes:
For each node $x$:
For heap $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]:
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]:
In [2]:
plt.imshow(plt.imread('./res/fig19_decrease.png'))
Out[2]:
CUT: As soon as the second child has been lost, we cut $x$ from its parent, making it a new root.
CASCADING-CUT: because $x$ might be the second child cut from its parent $y$ since the time that $y$ was linked to another node, we perform a cascading-cut operation on $y$.
In [3]:
#Exercises