\documentclass[12pt]{article}
\usepackage[letterpaper, margin=1.2in]{geometry}
\newtheorem{theorem}{Theorem}
\newtheorem{proof}{Proof}

\usepackage{amsfonts,amsmath,amssymb,enumerate}

% dot product
\usepackage{graphicx}

\makeatletter
\newcommand*\bigcdot{\mathpalette\bigcdot@{.5}}
\newcommand*\bigcdot@[2]{\mathbin{\vcenter{\hbox{\scalebox{#2}{$\m@th#1\bullet$}}}}}
\makeatother

\newcommand{\A}{\mathcal{A}}

% for plots
\usepackage{graphicx}
\graphicspath{ {./images/} }

% for textboxes
\usepackage{mdframed}

% for table
\usepackage{booktabs}

\DeclareMathOperator{\adj}{adj}
\DeclareMathOperator{\STP}{STP}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\mincover}{min-cover}
\DeclareMathOperator{\poly}{poly}
\DeclareMathOperator{\vdeg}{deg}
\DeclareMathOperator{\nll}{null}
\DeclareMathOperator{\col}{col}
\DeclareMathOperator{\Span}{Span}
\DeclareMathOperator{\range}{range}
\DeclareMathOperator{\proj}{proj}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\row}{row}
\DeclareMathOperator{\si}{si}
\DeclareMathOperator{\cl}{cl}

\DeclareMathOperator{\oc}{oc}

\usepackage{algpseudocode}
\usepackage[ruled, linesnumbered]{algorithm2e}

% absolute value
\usepackage{mathtools}
\DeclarePairedDelimiter\abs{\lvert}{\rvert}
\DeclarePairedDelimiter\norm{\lVert}{\rVert}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\DeclarePairedDelimiter\paren{\lparen}{\rparen}
\DeclarePairedDelimiter\of{\lparen}{\rparen}
\DeclarePairedDelimiter\br{\lbrack}{\rbrack}
\DeclarePairedDelimiter\ang{\langle}{\rangle}
\DeclarePairedDelimiter\cly{\lbrace}{\rbrace}
\DeclarePairedDelimiter\set{\lbrace}{\rbrace}

\usepackage{fancyvrb}

\definecolor{commentsColor}{rgb}{0.497495, 0.497587, 0.497464}
\definecolor{keywordsColor}{rgb}{0.000000, 0.000000, 0.635294}
\definecolor{stringColor}{rgb}{0.558215, 0.000000, 0.135316}

\usepackage{xcolor}
\definecolor{stringColor}{rgb}{0.497495, 0.497587, 0.497464}
\definecolor{keywordsColor}{rgb}{0.000000, 0.000000, 0.635294}
\definecolor{commentsColor}{rgb}{0.558215, 0.000000, 0.135316}

\usepackage{listings}
\usepackage{hyperref}
\lstset{
  language=C++,
  columns=fullflexible,
  basicstyle=\ttfamily,
  commentstyle=\mycommentstyle,
  breaklines=true,
  escapechar=\$,
  rulecolor = \color{gray},
  frame=none,
  keywordstyle=\color{blue},
  stringstyle=\color{stringColor},
  commentstyle=\color{commentsColor}\textit,
  numbers = none,
  xleftmargin=0.5in
}
\hypersetup{
  colorlinks,
  linkcolor=blue,
}

% set notation
\usepackage{braket}

\makeatletter
\let\oldabs\abs
\def\abs{\@ifstar{\oldabs}{\oldabs*}}
%
\let\oldnorm\norm
\def\norm{\@ifstar{\oldnorm}{\oldnorm*}}
\makeatother

% for drawing trees
\usepackage{tikz}   	
\usetikzlibrary{patterns,calc,chains,shapes.multipart,arrows,positioning,shapes,automata,fit,shadows,arrows.meta,trees}

\usepackage{adjustbox}
% code
\usepackage{fancyvrb}

\renewcommand{\A}{\mathcal{A}}
\newcommand{\Z}{\mathcal{Z}}
\newcommand{\T}{\mathcal{T}}
\renewcommand{\L}{\mathcal{L}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\M}{\mathcal{M}}
\newcommand{\odd}{\mathrm{odd}}
\newcommand{\even}{\mathrm{even}}
\renewcommand{\vec}{\mathbf}
\newcommand{\eps}{\epsilon}
\newcommand{\B}{\mathcal{B}}
\renewcommand{\Z}{\mathbb{Z}}

\usepackage{calc}

\setcounter{secnumdepth}{0}

% \usepackage{draftwatermark}
% % \SetWatermarkLightness{0.8}
% \SetWatermarkScale{4}

%%%% a few things that are needed for the data base, but mostly ignored here
\usepackage{ifthen} % for version control
\usepackage{todonotes}

\newenvironment{solution}
{
\begin{mdframed}[linewidth=2pt, linecolor=gray]
\color{blue} \textbf{Solution ideas.}
}
{
\end{mdframed}
}

\usepackage{soul}

\usepackage{multicol}

\begin{document}
\parindent=0pt
\setlength{\parskip}{0.5em}

\begin{mdframed}[linewidth=1pt]
CS240E W25 \hfill \textbf{Tutorial 2} \hfill Jan. 17
\end{mdframed}

\subsubsection{Overview}

\begin{multicols}{2}
\begin{itemize}
\item Heapify
\item Merging Binary Heaps
\item Increase-key
\item Binomial Heaps
\item Converting between Binary Trees and Multiway Trees
\end{itemize}
\end{multicols}

\noindent\rule{\textwidth}{0.5pt}

\subsubsection{Problems}

\textbf{Q1. Heapify.}

Execute heapify on the following array (displayed here in tree form with array indices as subscripts):

\begin{center}
        \begin{tikzpicture}[level distance=32pt,
                every node/.style={circle,draw,inner sep=2pt, minimum size=1.5em},
                level 1/.style={sibling distance=90pt},
                level 2/.style={sibling distance=50pt},
                level 3/.style={sibling distance=50pt}]
                \node [fill=white] (r2) {$3_0$}
                        child {node {$5_1$}
                                child{node {$7_3$}}
                                child{node {$10_4$}}
                        }
            child {node {$8_2$}
                                child{node {$2_5$}}
                                child{node {$14_6$}}
                        };
        \end{tikzpicture}
\end{center}

\textbf{Q2. Merging Binary Heaps.}

Let $H_1$ and $H_2$ be two binary heaps that both store exactly $2^h-1$ items for some $h \in \mathbb{N}$.
Show how to merge these two heaps. The run-time should be $O(h)$, presuming both heaps
are stored as trees (not arrays), and the output must again be a binary heap (so satisfy the structural property).

\textbf{Q3. Multi-way tree.}
Let $T$ be a multi-way tree, i.e., nodes can have arbitrarily many children.
\begin{enumerate}
\item[(a)] Recall from lecture that there is a simple way to convert a multi-way tree $T$ into a binary tree $T'$:
        Each node of $T$ also becomes a node in $T'$, its leftmost child in $T$ becomes
        the left child in $T'$, and its sibling to the right in $T$ becomes the right
        child in $T'$.  Show the binary tree that you get in this way if you start with the following multi-way tree:
        
\begin{center}
\begin{tikzpicture}[level distance=32pt,
        every node/.style={circle,draw,inner sep=2pt, minimum size=1.5em},
        level 1/.style={sibling distance=50pt},
        level 2/.style={sibling distance=40pt},
        level 3/.style={sibling distance=10pt}]
        \node [fill=white] (r2) {11}
                child {node {7}
                        child{node {5}}
                        child{node {6}}
                }
                child {node {1}
                        child{node {2}}
                }
    child {node {16}
                        child{node {21}}
                        child{node {0}}
                };
\end{tikzpicture}
\end{center}

\item[(b)] For which binary trees $T'$ is there a multiway tree $T$ that it corresponds to?
Justify your answer by explaining how you would convert such a binary tree $T'$
into a multiway tree $T$.

\item[(c)] Assume $T'$ is a flagged tree that satisfies the order-property of binomial heaps.
What order-property does the corresponding multiway tree $T$ have?
\end{enumerate}

\textbf{Q4. Increase-key.}

\begin{enumerate}
    \item[(a)] Here is a binary heap. Show the intermediate steps when performing \verb`increase-key` $(8,12)$ using fix-up.

    \begin{center}
    \begin{tikzpicture}[level distance=32pt,
                every node/.style={circle,draw,inner sep=2pt, minimum size=1.5em},
                level 1/.style={sibling distance=10
                0pt},
                level 2/.style={sibling distance=70pt},
                level 3/.style={sibling distance=40pt}]
                \node [fill=white] (r2) {$10_0$}
                        child {node {$8_1$}
                                child{node {$7_3$}
                                        child{node {$3_7$}}
                                        child{node {$5_8$}}
                                }
                                child{node {$4_4$}
                                        child{node {$2_9$}}
                                        child[missing]
                                }
                        }
            child {node {$9_2$}
                                child{node {$1_5$}}
                                child{node {$6_6$}}
                        };
        \end{tikzpicture}
        \end{center}

    (Recall that the first parameter of \verb`increase-key` is a reference to a node, so in this case \verb`increase-key` $(8,12)$ means increase the key of the node at index $8$ to $12$.)

    \item[(b)] Here is a multiway tree with the heap-order property. Show the intermediate steps when performing \verb`increase-key` $(14,19)$ using fix-up. 

    \begin{center}
        \begin{tikzpicture}[level distance=32pt,
                every node/.style={circle,draw,inner sep=2pt, minimum size=1.5em},
                level 1/.style={sibling distance=100pt},
                level 2/.style={sibling distance=30pt},
                level 3/.style={sibling distance=30pt},
                level 3/.style={sibling distance=30pt}]
                \node [fill=white] (r2) {$20_0$}
                        child {node {$10_1$}
                                child{node {$5_4$}
                                        child{node{$3_{13}$}}
                                        child{node{$4_{14}$}}
                                        child[missing]
                                }
                                child{node {$7_5$}}
                                child{node {$9_6$}}
                        }
                        child {node {$12_2$}
                                child{node {$1_7$}}
                                child{node {$6_8$}}
                                child{node {$8_9$}}
                        }
                        child {node {$16_3$}
                                child{node {$11_{10}$}}
                                child{node {$13_{11}$}}
                                child{node {$15_{12}$}}
                        };
        \end{tikzpicture}
        \end{center}

    (Recall from lecture that we can't usually store multiway trees in arrays because nodes 
    can have any number of children. But if we restrict this to each node having at most three children, then we
    can store it in an array, as shown by the indices in this example. Bonus question: How would you change the binary heap algorithms
    presented in class to work with this kind of tree structure?)

    \item[(c)] What is the binary tree that corresponds to the multiway tree from (b)? 
\end{enumerate}

\textbf{Q5. Binomial heaps.}
Perform the following operations on the binomial heap below, in order:
\begin{center}
\begin{tikzpicture}[level distance=32pt,
        every node/.style={circle,draw,inner sep=2pt, minimum size=1em},
        level 1/.style={sibling distance=50pt},
        level 2/.style={sibling distance=40pt},
        level 3/.style={sibling distance=30pt}]
        \node(r1) {10}
                child {node {8}
                        child {node {6}}
                        child {node {9}}
                }
                child {edge from parent[draw=none]};
        \node [right=55pt of r1,fill=white] (r2) {20}
                child {node {14}
                        child {node [left=2pt] {2}
                                child {node {0}}
                                child {node {5}}
                                }
                        child {node [right=2pt] {10}
                                child {node {7}}
                                child {node {12}}}}
                child {edge from parent[draw=none]};

        \draw [dashed] (r1) -- (r2);

\end{tikzpicture}
\end{center}
\begin{itemize}
        \item Call \verb`insert(4)`.
        \item Call \verb `merge` with the following binomial heap:
        \begin{center}

        \begin{tikzpicture}[level distance=32pt,
                every node/.style={circle,draw,inner sep=2pt, minimum size=1em},
                level 1/.style={sibling distance=50pt},
                level 2/.style={sibling distance=40pt},
                level 3/.style={sibling distance=30pt}]
                \node (r1) {19};
                \node [right=50pt of r1,fill=white] (r2) {11}
                        child {node {7}
                                child{node {5}}
                                child{node {6}}
                        }
                        child {edge from parent[draw=none]};
                \draw [dashed] (r1) -- (r2);
        \end{tikzpicture}
        \end{center}
        \item Call \verb`deleteMax()`.
\end{itemize}

\end{document}

