%% This LaTeX-file was created by <jl> Wed Feb  4 13:10:22 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}

day8 2/4/98 ``I'd do it, but it probably doesn't work.''


\section{Treaps, continued}


\subsection{timing analses for search}

\begin{itemize}
\item \( p\{i=ancestor(j)\}=\frac{1}{j-i+1} \) with \( i\leq j \) = number of right turns in descending the tree = In a random ordering
among \( \{i,i+1,...,j\} \), the probability that \( i \) is first.
\item \( p\{i=ancestor(j)\}=\frac{1}{j-i+1} \) with \( j\leq i \) = number of left turns in descending the tree = In a random ordering
among \( \{j,j+1,...,i\} \), the probability that \( i \) is first.
\end{itemize}
Then the expected number of ancestors of j is \( \sum _{i=1}^{n}\frac{1}{|j-i|+1}\leq 2\sum _{i=1}^{n}\frac{1}{i}=2*ln(n) \)


\subsection{number of rotations in a delete.}

The expected number of rotations in a delete is less than 2. The number of rotations
is less than the sum of the rightmost branch (right spine) of the left child
and the leftmost branch (left spine) of the right child.

analyse the right spine. 

\( p_{i\leq j}\{j=ancestor(i)\wedge i\in rightspine\} \) = random order of \( \{i,...,j\} \) with j first and i second = \( \frac{1}{(j-i+1)(j-i)} \)

let size of right spine = \( G_{j} \). Then \( E(G_{j})=\sum _{i=2}^{j-1}\frac{1}{i(i-1)}=\frac{j-1}{j} \)


\subsection{dynamic treaps}

When a particular element is accessed adjust it's priority so the elements float
towards the top of the treap.

old \( p(k) \) uniform in \( [0,1] \).

new \( p(k)=min(p(k),random\in [0,1]) \)


\section{Binomial and Fibonacci heaps}


\subsection{An algorithm using these structures}

\begin{itemize}
\item \( G=(V,E) \) an undirected graph
\item \( |V|=n \)
\item \( |E|=m \)
\item \( l:E\rightarrow R^{+} \)
\item extend \( l \) as \( l(v,w)=\infty  \) if \( (v,w)\notin E \), 0 if \( v=w \), and \( l(e) \) where \( e=(v,w) \) otherwise
\item \( P \) = path = \( e_{1},...,e_{k} \). 
\item \( l(P)=\sum _{i=1}^{k}l(e_{i}) \)
\item \( d(u,v)= \) length of minimum weight path
\end{itemize}

\subsubsection{Dijkstra's algorithm}

\begin{enumerate}
\item \( W=V-\{s\} \), \( D(s)=0 \)
\item \( \forall u\in W \) do \( D(u)=l(s,u) \)
\item while \( W\neq 0 \)
\item \( u=Extractmin(W,D) \)
\item \( \forall (u,v)\in E \) with \( v\in W \), \( D(v)=min(D(v),D(u)+l(u,v)) \)
\item endwhile
\end{enumerate}

\subsubsection{timing analyses}

with a good data structure you can get:

\( \begin{array}{cccc}
 & \# & cost/op & totalcost\\
step2(insert) & n & O(1) & O(n)\\
step4(deletemin) & n & O(log(n)) & O(n*log(n))\\
step5(decrement) & m & O(1) & O(m)
\end{array} \)


\subsection{binomial heap operations}

\begin{itemize}
\item makeheap(i) O(1)
\item findmin(h) O(1)
\item insert(h,i) O(1)
\item deletemin(h) O(log(n))
\item meld(h,h') O(1) or O(log(n))
\item decrement(h,i,\( \Delta  \)) (only efficient with fibonacci heaps) O(1)
\item delete(h,i) (only efficient with fibonacci heaps) O(log(n))
\end{itemize}

\subsection{definition of binomial trees}

\begin{itemize}
\item \( B_{0} \) = 1 element tree
\item \( B_{1} \) = 2 element tree with one a root of the other
\item \( B_{2} \) = 4 element tree composed of 2 \( B_{1} \) trees joined at the root.
\item In general \( |B_{i}|=2^{i} \) and the degree of the root node is i
\end{itemize}
Since the number of elements in each \( B_{i} \) doubles with i, you can have a heap of
arbitrariy (integer) size represented as a set of \( B_{i} \) trees of different sizes.

\begin{itemize}
\item a set of trees is in heap order if each tree is ordered and points to the min.
\item rank(x)=\# of children of x
\end{itemize}

\subsection{operation implementations}


\subsubsection{meld(h,h')}

Essentially, you just do binary addition between the sets of trees in h and
h'. The amortized cost of adding an element to the heap is 2.

\end{document}