%% This LaTeX-file was created by <jcl> Thu Feb 12 21:48:31 1998
%% LyX 0.12 (C) 1995-1998 by Matthias Ettrich and the LyX Team

%% Do not edit this file unless you know what you are doing.
\documentclass{article}
\usepackage[T1]{fontenc}

\makeatletter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\newcommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\spacefactor1000}

\makeatother

\begin{document}

day 9: 2/9/98 ``This is a big mess.''


\section{Binomial Tree's, continued}


\subsection{some definitions}

\begin{itemize}
\item \( |B_{i}|=2^{i} \)
\item \( rank(node)=\#children \)
\item \( rank(tree)=rank(root) \)
\end{itemize}

\subsection{insertion}

Make a singleton tree then meld it with the tree you wish to insert into. This
is amortized \( O(1) \).


\subsection{lazy meld}

Relax the restriction that there be only one tree of a particular \( B_{i} \). Concatenate
2 lists of trees in the meld, updating the min pointer to the min of each heap.


\subsubsection{Find min}

Just follow the min pointer through the heap


\subsubsection{delete min}

Remove some root and consider each subtree a tree. It will be necessary to inspect
all trees to find the new min pointer. Might as well do real melds at the same
time. \( O(log(n)) \).


\section{Fibonacci heaps}

Fibonacci heaps are binomial heaps with these exceptions:

\begin{itemize}
\item each node may be missing at most 1 child
\item Root may be missing any number of children
\end{itemize}

\subsection{Invariant}

\begin{itemize}
\item \( rank(t)\leq O(log(n)) \)
\end{itemize}

\subsection{decrement}

To decrement, promote nodes to the top level and decrement most of the time. 

\( decrement(h,x,\Delta ) \)

\begin{enumerate}
\item change priority of x
\item if \( x\neq root \) then let \( y=parent(x) \)
\end{enumerate}
\begin{itemize}
\item promote x to a new tree and mark(x)
\item cascade-cut(y)
\end{itemize}
\( cascade-cut(y) \)

\begin{enumerate}
\item \( z=parent(y) \)
\item if \( y\neq root \) then if \( mark(y)=\emptyset  \) then \( mark(y)=true \) else \( cut(y) \) and \( cascade-cut(z) \)
\end{enumerate}
\( cut(y) \)

\begin{enumerate}
\item promote y to a root
\end{enumerate}

\subsection{analysis}

let f = a potential function = \( \# \) of trees + 2 {*} \( \# \) of marks.

Hmm.. These notes are indecipherable. I'll grab some stuff from a book of mine.
``Algorithms from P to NP'' by Moret and Shapiro. This is pretty much verbatim.


\paragraph{Lemma:}

Let x be any node in a Fibonacci heap and let the current children of x be orderd
from ealiest to latest according to the time at whichc they were linked to x.
Then the rank of the ith child is at least \( i-2 \). \( rank(y)\geq i-2 \) where y = i'th child of x


\paragraph{proof:}

When y was linked to x, x must alread have had at least i-1 children, because
children could since have disappeared (due to cuts), but any children added
subsequently would be farther down in the order. Since x and y were linked,
they had the same rank at that time, so that y itself had at least \( i-1 \) children.
Since y has not been cut, it can have lost at most one child since that time
and hence still has at least \( i-2 \) children.


\paragraph{corollary:}

A node of ranke \( k \) in a fibonacci heap has at least \( F_{k+2} \) descendents where \( F_{k} \) is
the \( k \)th fibonacci number.


\paragraph{proof:}

Let \( S_{k} \) be the size of the smallest possible subtree in any Fibonacci heap such
that its root has rank \( k \). We claim that we have \( S_{k}=F_{k+2} \). We have \( S_{0}=1 \) and \( S_{1}=2 \). The preceeding
lemma gives the recurrence \( S_{k}\geq \sum _{i=2}^{k}S_{i-2}+2 \). The inequality is exact because \( S_{k} \) was was specified
to be minimal and such a tree does exist, giving: \( S_{k}=S_{k-1}+S_{k-2} \). This implies \( S_{k}=F_{k+2} \).

\end{document}