# Lecture 2 - Fibonacci Heap and its Application
###### tags: `Algorithm`
## Priority Queue
A data structure supporting the following operations
+ $Insert$: insert element $x$
+ $FindMin$: return minimum element
+ $DeleteMin$: return and delete minimum element
+ $DecreaseKey$: decrease key of element $x$ to $k$
### Applications
+ *Dijkstra*'s shortest path algorithm
```python
Maintain a priority queue Q on vertices
Put s into Q with d(s)=0, mark s
Repeat
Delete the minimum vertex v from Q, mark v
For every edge (v,w)
if w is not marked
if w is in Q, update the key d(w)=min{d(w),d(v)+l(v,w)}
else put w in Q with d(w)=d(v)+l(v,w)
Until Q is empty
```
+ $n\ Insert$, $n\ DeleteMin$, $m\ DecreaseKey$
+ *Prim*'s MST algorithm
```python
Maintain a priority queue Q on vertices
Put s into Q with d(s)=0, mark s
Repeat
Delete the minimum vertex v from Q, mark v
For every edge (v,w)
if w is not marked
if w is in Q, update the key d(w)=min{d(w), l(v,w)}
else put w in Q with d(w)=l(v,w)
we keep track of the vertex v that gives w the minimum d(w)
Until Q is empty
```
+ $n\ Insert$, $n\ DeleteMin$, $m\ DecreaseKey$
+ Event-driven simulation
+ Huffman encoding
+ Heapsort
## Binary Heap
### Heap
A heap is a specialized tree-based data structure that satisfies the heap property
+ If $A$ is a parent node of $B$ then the key of node $A$ is **smaller** than the key of node $B$
+ We consider **min-heap**
### Binary Heap
#### Definition
+ Almost complete binary tree
+ Filled on all levels, except last, where filled from left to right
+ **Min-heap** ordered
+ Every child greater than (or equal to) parent
#### Property
+ Min element is in root
+ Heap with $N$ elements has height = $\lfloor \log_2 N\rfloor$
#### Implementation
+ Use an array: no need for explicit parent or child pointers
+ $Parent(i) = \lfloor i/2\rfloor$
+ $Left(i) = 2i$
+ $Right(i) = 2i+1$
+ $Insert$: insert element $x$ into heap
+ Insert into next available slot
+ Bubble up until it's heap ordered
+ Peter principle: nodes rise to level of incompetence
+ $O(\log N)$ operation
+ $Decrease Key$: decrease key of element $x$ to $k$
+ Bubble up until it's heap ordered
+ $O(\log N)$ operation
+ $Delete Min$: delete minimum element from heap
+ Exchange root with rightmost leaf
+ Bubble root down until it's heap ordered
+ Power struggle principle: better subordinate is promoted
+ $O(\log N)$ operation
+ $Union$
+ Combine two binary heaps $H_1$ and $H_2$ into a single heap
+ No easy solution
+ $\Omega(N)$ operations apparently required
+ Can support fast union with fancier heaps
#### Application
+ *Dijkstra*'s SSSP algorithm and *Prim*'s MST algorithm: $O(m\log n)$
## Binomial Heap *(Vuillemin, 1978)*
### Binomial Tree
+ Recursive definition: 
+ Rank of a node $x$: the number of children of $x$
+ Rank of a tree: the rank of the root of the tree
+ Property of $B_k$
+ Number of nodes $=2^k$
+ Height $= k$
+ Degree of root $= k$
+ Deleting root yields binomial trees $B_{k-1}, … , B_0$
+ Proof: Induction on $k$
+ $B_k$ has $\begin{pmatrix}k\\i\\\end{pmatrix}$ nodes at depth $i$
+ Every combination of $i$ elements in $\{k-1,k-2,...,0\}$ correspond to a node in depth $i$, based on the degrees of nodes from the root to it.
+ For example, $k=4, i=2$
### Definition
Sequence of binomial trees that satisfy binomial heap property
+ Each tree is min-heap ordered
+ $0$ or $1$ binomial tree of each rank
+ If there are two trees of the same rank, then merge them
### Implementation
+ Represent trees using left-child, right sibling pointers
+ Three links per node (parent, left, right)
+ Roots of trees connected with singly linked list
+ Degrees of trees strictly decreasing from left to right
### Property
+ Min key contained in roots of $B_0, B_1, . . . , B_k$
+ Contains binomial tree $B_i\iff b_i=1$ where $b_n…b_2b_1b_0$ is binary representation of $N$, since $B_i$ has $2^i$ nodes
+ At most $\lfloor\log_2 N\rfloor+1$ binomial trees
+ Height $\leq\lfloor\log_2 N\rfloor$
### Operation
+ $Union$: create heap $H$ that is union of heaps $H'$ and $H''$
+ **Mergeableheaps**
+ Easy if $H'$ and $H''$ are each rank kbinomial trees
+ Connect roots of $H'$ and $H''$
+ Choose smaller key to be root of $H$
+ Analogous to binary addition
+ Running time: $O(\log N)$
+ $DeleteMin$: delete node with minimum key in binomial heap $H$
+ Find root $x$ with min key in root list of $H$, and delete
+ $H'\leftarrow$ broken binomial trees
+ $H\leftarrow Union(H', H)$
+ Running time: $O(\log N)$
+ $DecreaseKey$: decrease key of node $x$ in binomial heap $H$
+ Suppose $x$ is in binomial tree $B_k$
+ Bubble node $x$ up the tree if $x$ is too small
+ Running time: $O(\log N)$
+ Proportional to depth of node $x\leq\lfloor\log_2 N\rfloor$
+ $Delete$: delete node $x$ in binomial heap $H$
+ $DecreaseKey(x,-\infty)$
+ $DeleteMin$
+ Running time $O(\log N)$
+ $Insert$: insert a new node $x$ into binomial heap $H$
+ $H' ← MakeHeap(x)$
+ $H ← Union(H', H)$
+ Running time: $O(\log N)$
+ Sequence of $Insert$s:
+ Insert a new node $x$ into binomial heap $H$
+ If $N=.......0_2$, then only $1$ steps
+ If $N=......01_2$, then only $2$ steps
+ If $N=.....011_2$, then only $3$ steps
+ $...$
+ If $N=11111111_2$, then $\log_2N$ steps
+ Inserting $1$ item can take $\Omega(\log N)$ time
+ But, inserting sequence of $N$ items takes $O(N)$ time
+ $(N/2)(1)+(N/4)(2)+(N/8)(3)+...\leq 2N$
+ Amortized analysis
## Fibonacci Heap (*Fredman and Tarjan, 1986*)
### History
+ Ingenious data structure and analysis
+ Original motivation: improve *Dijkstra*'s shortest path algorithm from $O(m\log n)$ to $O(m + n\log n)$
### Basic idea
+ Similar to binomial heaps, but less rigid structure
+ Binomial heap: **eagerly** consolidate trees after each $Insert$
+ Fibonacci heap: **lazily** defer consolidation until next $DeleteMin$
### Definition
+ Set of **heap-ordered** (each parent smaller than its children) trees
+ Maintain pointer to minimum element $\to\ FindMin$ takes $O(1)$ time
+ Set of marked nodes (has lost one child, if it loses another child, it will be cut)
#### Notation
+ $n$: number of nodes in heap
+ $rank(x)$: number of children of node $x$
+ $rank(H)$: max rank of any node in heap $H$
+ $trees(H)$: number of trees in heap $H$
+ $marks(H)$ = number of marked nodes in heap $H$
#### Potential function
+ Potential of heap $H$: $\phi(H)=trees(H)+2marks(H)$
+ Amortized time: actual time $+$ change of potential
+ Initially sum of potentials is $0$, potentials remain positive all the time
+ Thus, real total time $=$ total amortized time $-$ final potential
+ So total time is at most the total amortized time
### Operation
+ $Insert$
+ Create a new singleton tree
+ Add to root list; update min pointer (if necessary)
+ Actual cost: $O(1)$
+ Change in potential: $+1$
+ Amortized cost: $O(1)$
+ $DeleteMin$
+ $Linking$: Make larger root be a child of smaller root
+ Delete min; meld its children into root list; update min
+ Consolidate trees so that no two roots have same rank
+ Same as in binomial heap
+ Actual cost: $O(rank(H))+O(trees(H))$
+ $O(rank(H))$ to meld min's children into root list
+ $O(rank(H))+O(trees(H))$ to update min
+ $O(rank(H))+O(trees(H))$ to consolidate trees
+ Change in potential: $O(rank(H))-trees(H)$
+ $trees(H')≤rank(H)+1$ since no two trees have same rank
+ $∆\phi(H)= trees(H')-trees(H)≤rank(H)+1-trees(H)$
+ Amortized cost: $O(rank(H))$
+ Is amortized cost of $O(rank(H))$ good?
+ Yes, if only $Insert$ and $DeleteMin$ operations
+ In this case, all trees are binomial trees (we only $Link$ trees of equal rank)
+ This implies $rank(H)\leq\log_2 n$
+ We'll implement $DecreaseKey$ so that $rank(H) = O(\log n)$
+ $DecreaseKey$
+ Intuition for deceasing the key of node $x$
+ If heap-order is not violated, just decrease the key of $x$
+ Otherwise, cut tree rooted at $x$ and meld into root list
+ To keep trees flat: as soon as a node has its second child cut, cut it off and meld into root list and unmark it
+ Case $1$: heap order not violated
+ Decrease key of $x$
+ Change heap min pointer (if necessary)
+ Case $2a$: heap order violated
+ Decrease key of $x$
+ Cut tree rooted at $x$, meld into root list, and unmark
+ If parent $p$ of $x$ is unmarked (hasn't yet lost a child), mark it
+ Case $2b$
+ Decrease key of $x$
+ Cut tree rooted at $x$, meld into root list, and unmark
+ If parent $p$ of $x$ is unmarked (hasn't yet lost a child), mark it
Otherwise, cut $p$, meld into root list, and unmark
+ And do so recursively for all ancestors that lose a second child
+ Question: why we have a marked root node
+ Actual cost: $O(c)$
+ $O(1)$ time for changing the key
+ $O(1)$ time for each of $c$ cuts, plus melding into root list
+ Change in potential: $O(1)-c$
+ $trees(H')=trees(H)+c$
+ $marks(H') ≤ marks(H)-c+2$
+ $∆\phi≤c+ 2(-c+2)=4-c$
+ Amortized cost: $O(1)$
+ $Union$: combine two Fibonacci heaps
+ Representation: root lists are circular, doubly linked lists
+ Actual cost: $O(1)$
+ Change in potential: $0$
+ Amortized cost: $O(1)$
+ $DeleteMin$: delete node $x$
+ $DecreaseKey$ of $x$ to $-∞$
+ $DeleteMin$ element in heap
+ Amortized cost: $O(rank(H))$
+ $O(1)$ amortized for $DecreaseKey$
+ $O(rank(H))$ amortized for $DeleteMin$
### Bounding the Rank
#### Lemma: Fix a point in time. Let $x$ be a node, and let $y_1, …, y_k$ denote its children in the order in which they were linked to $x$. Then $$rank(y_i)\geq\begin{cases}0,& \text{if $i=1$} \\ i-2,& \text{if $i\geq1$} \end{cases}$$
+ 
+ When $y_i$ was linked into $x$, $x$ had at least $i-1$ children $y_1, …, y_{i-1}$
+ Since only trees of equal rank are linked, at that time $rank(y_i)=rank(x_i)≥i-1$
+ Since then, $y_i$ has lost at most one child or $y_i$ would have been cut
+ Thus, right now $rank(y_i)≥i-2$
#### Definition: Let $F_k$ be smallest possible tree of rank $k$ satisfying property
+ Solve: $F_k≥F_{k-2}+F_{k-3}+…+F_0+1$
#### Lemma (Fibonacci fact): $F_k≥\phi^k$, where $\phi=\frac{1+\sqrt5}{2}\approx 1.618$
+ Induction on $k$
+ Base case: $F_0 = 0$, $F_1=1$ (slightly non-standard definition)
+ $F_{k+2}=F_{k}+F_{k+1}\geq\phi^k+\phi^{k+1}=\phi^k(1+\phi)=\phi^k(\phi^2)=\phi^{k+2}$
#### Corollary: $rank(H)\leq\log_{\phi}n = O(\log n)$
### Application
+ *Dijkstra*'s SSSP algorithm and *Prim*'s MST algorithm: $O(m+n\log n)$
## Summary
|Operation|Linked List|Binary Heap|Binomial Heap|Fibonacci Heap*|
|---|---|---|---|---|
|$MakeHeap$|$O(1)$|$O(1)$|$O(1)$|$O(1)$|
|$isEmpty$|$O(1)$|$O(1)$|$O(1)$|$O(1)$|
|$Insert$|$O(1)$|$O(\log n)$|$O(\log n)$|$O(1)$|
|$DeleteMin$|$O(n)$|$O(\log n)$|$O(\log n)$|$O(\log n)$|
|$DecreaseKey$|$O(n)$|$O(\log n)$|$O(\log n)$|$O(1)$|
|$Delete$|$O(n)$|$O(\log n)$|$O(\log n)$|$O(\log n)$|
|$Union$|$O(1)$|$O(n)$|$O(\log n)$|$O(1)$|
|$FindMin$|$O(n)$|$O(1)$|$O(\log n)$|$O(1)$|
$n$: number of elements in priority queue
\*amortized analysis
Sign in with Wallet
Connect another wallet