source_heap.tex

\input{preamble}

\begin{document}
\section{Initiales}
\SidebarCite{gh:episode-recursion}
\SidebarCite{gh:tikzpingus}
\begin{frame}{Disclaimer}
    \begin{itemize}[<+(1)->]
        \itemsep12pt
        \item Dieser \say{Heap} hat nichts mit dem aus der Rekursions-\allowbreak Episode zu tun!
        \item Wir beschränken uns auf Heap-\textit{Bäume}
        \item Wir ignorieren Rotationen
        \item Die Folien sind in \(\sim\)\,3.5 Stunden entstanden\smash{\raisebox{-2pt}{\textsuperscript{also reduziert}}}
    \end{itemize}
\end{frame}
\SidebarReset

\section{Arten von Heaps}
\subsection{Max-Heap vs. Min-Heap}
\savebox\pinguC{\tikz[baseline=-.6ex]{\fill[shadeA] circle[radius=2.15pt];}~~\thinspace}
\begin{frame}{Die Muster-Kinder}
\begin{columns}[c]
    \begin{column}{.45\linewidth}
\onslide<2->{\centering\heap{[4[2[-2][-3]][1]]}\bigskip\par}
    \onslide<4->{\color{gray}\onslide<6->{\hskip-\wd\pinguC\relax\usebox\pinguC}\textbf{Max}-Heap\par
    {\textcolor{gray}{\scriptsize\(\text{Eltern} \geq \text{Kinder}\)}}}
    \end{column} \begin{column}{.45\linewidth}
\onslide<3->{\centering\heap{[-3[-2[2][4]][1]]}\bigskip\par}
    \onslide<5->{\color{gray}\textbf{Min}-Heap\par
    {\textcolor{gray}{\scriptsize\(\text{Eltern} \leq \text{Kinder}\)}}}
    \end{column}
\end{columns}
\end{frame}

\subsection{Die Anatomie eines Heaps}
\savebox\pinguA{\tikz{\pingu[monocle left, right eye wink, right wing grab,bow tie=paletteA]}}%
\savebox\pinguB{\tikz{\pingu[wings shock, eyes shiny, princess crown]}}%
\begin{frame}{Die Anatomie}
    \onslide<2->{\centering\heap{%
        [42,name=root[19,name=inner1[7,name=inner2[3,name=leaf1][-2,name=leaf2]][8,name=leaf3]][-5,name=inner3[-9,name=leaf4]]]%
        \onslide<3->{\fill[shadeA] (root.north)++(0,2mm) circle [radius=2.15pt] node[left=1.65mm,paletteA,font=\sbfamily] (dr) {Wurzel};
        \node[below=-4pt,gray,font=\scriptsize\itshape] at (dr.south) {root};}
        \pgfinterruptboundingbox
        \onslide<4->{\fill[shadeB] (inner1.north)++(0,2mm) circle [radius=2.15pt] node[left=1.65mm,paletteB,font=\sbfamily] (di) {Innerer Knoten};
        \node[below=-4pt,gray,font=\scriptsize\itshape] at (di.south) {inner node};
        \foreach\i in {2,3} {\fill[shadeB] (inner\i.north)++(0,2mm) circle [radius=2.15pt];}}
        \onslide<5->{\fill[shadeD] (leaf1.west)++(-2mm,0) circle [radius=2.15pt] node[left=1.65mm,paletteD,font=\sbfamily] (dl) {Blatt};
        \node[below=-4pt,gray,font=\scriptsize\itshape] at (dl.south) {leaf};
        \foreach\i in {2,3,4} {\fill[shadeD] (leaf\i.west)++(-2mm,0) circle [radius=2.15pt];}}
        \endpgfinterruptboundingbox
        \onslide<7->{
            \node[right=1.25cm,gray] (niveau) at (dr-|inner3) {\textbf{Ebene}};
        }
        \pgfonlayer{background}
            \foreach[count=\i] \x in {root,inner1,leaf3,leaf1} {
                \onslide<\the\numexpr\i+7\relax->{
                    \node[gray,font=\sbfamily] (dn\i) at(\x-|niveau) {\the\numexpr\i-1\relax};
                    \draw[lgray!90!white,densely dashed, very thick] (dn\i.west) -- (dl.west|-dn\i.west);
                }
            }
        \endpgfonlayer
    }}
\begin{tikzpicture}[overlay,remember picture]
    \onslide<6->{%
        \node[below left=.25cm,yshift=.8cm,scale=.6] (pingu) at (current page.north east) {\rotatebox[origin=c]{180}{\usebox\pinguA}};
        \node[left,scale=.6,text width=6.75cm,align=center,yshift=-.33cm] at (pingu.west) {Blätter sind also Knoten ohne weitere Kindknoten.};
    }
    \onslide<12->{%
        \node[above right=-.66cm,scale=.6] (pingu) at (current page.south west) {\rotatebox[origin=c]{-45}{\usebox\pinguB}};
        \node[above=1.5mm,scale=.625,xshift=-1.65mm,gray,text width=5.5cm,align=center,yshift=-.33cm] at (pingu.north east) {Die Linien zwischen den Knoten heißen einfach \say{Kante} (\textit{edge}).};
    }
\end{tikzpicture}%
\end{frame}

\subsection{Ein formaler Blick}
\savebox\pinguA{\tikz{\pingu[eyes shock,wings shock,hair 3=paletteB, halo]}}%
\SidebarCite{gh:episode-recursion}
\SidebarCite{dive:bin-tree}
\begin{frame}{Formales}
\begin{itemize}[<+(1)->]
    \itemsep15pt
    \item Für uns ein Baum \begin{itemize}
        \item Graph \(G = (V, E)\) mit \(\abs{V}\) Knoten und \(\abs{E}\) Kanten
        \item \(V\) und \(E\) sind endlich
        \item Azyklisch \& zusammenhängend (\say{maximal azyklisch})
    \end{itemize}
    \item Sogar ein Binärbaum! \begin{itemize}
        \item Jeder Knoten hat maximal zwei Nachfolger
        \item Wir konzentrieren uns auf ausgewogene
    \end{itemize}
    \item Bäume lassen sich als rekursive Struktur auffassen
\end{itemize}
\begin{tikzpicture}[overlay,remember picture]
    \onslide<9->{%
        \node[below,xshift=-.5cm,yshift=.8cm,scale=.6] (pingu) at (current page.north east) {\rotatebox[origin=c]{135}{\usebox\pinguA}};
        \node[left,scale=.6,text width=6.25cm,align=center,yshift=-.33cm] at (pingu.west) {Eine sträflich oberflächliche Betrachtung etlicher cooler formaler Grundlagen.};
    }
\end{tikzpicture}%
\end{frame}
\SidebarReset

\section{Operationen}

\subsection{Heapify}
\savebox\pinguA{\heap{[3,name=3[4,name=4,edge={shadeA},edge label={node[midway, above left,paletteA] {\faFlash\ Max-Heap}}][2,name=2]]}}
\savebox\pinguB{\tikz{\pingu[left wing wave, pride flag left,sunglasses,tie=paletteD,glow=paletteD]}}%
\begin{frame}{Heapify}
\centering\onslide<2->{\usebox\pinguA}\onslide<3->{\qquad\raisebox{.5\ht\pinguA}{\tikz[baseline=-.6ex]{\draw[gray,ultra thick,-Kite] (0,0) -- (.75,0);}}\qquad\heap{[4[3][2]]}}
\vspace*{3em}
\begin{itemize}
    \item<4-> \textit{Up}-Heapify: Prüft Blätter \(\to\) Wurzel
    \item<5-> \textit{Down}-Heapify: Prüft Wurzel \(\to\) Blätter
\end{itemize}
\begin{tikzpicture}[remember picture,overlay]
    \onslide<6->{%
        \node[above right=.25cm,yshift=.33cm,scale=.6] (pingu) at (current page.south west) {\usebox\pinguB};
        \node[above=1mm,scale=.75,text width=4.5cm,align=center,font=\footnotesize\sffamily] at(pingu.north) {%
            Herstellung der Heap-Eigenschaft durch Vertauschungen!%
        };
    }
\end{tikzpicture}
\end{frame}

\subsection{Insert/Put}
\savebox\pinguA{\heap{[8[6[3][,lblob=shadeD,edge=shadeD,minimum size=0pt,inner sep=6pt]][5]]}}
\savebox\pinguB{\tikz{\pingu[hat=paletteC!89!black,eyes wink,heart=lgray,hat ribbon=paletteC]}}%
\begin{frame}{Insert\,/\,Put}
\begin{itemize}
    \itemsep8pt
    \item<2-> Auf der niedersten Ebene, so weit links wie möglich
    \item<3-> Anschließend: \textit{heapify}
\end{itemize}
\vspace*{3em}\par
\centering
\downsize\linewidth{$\color{gray}\onslide<4->{\underbrace{\strut\color{black}\onslide<4->{\usebox\pinguA}\onslide<5->{\qquad\raisebox{.5\ht\pinguA}{\tikz[baseline=-.6ex]{\draw[gray,ultra thick,-Kite] (0,0) to[edge node={node[above=4pt,font=\sbfamily]{9}}] (.75,0);}}}}_{\text{\textcolor{gray}{\LARGE\strut Insert}}}}$~$\color{gray}\onslide<5->{\underbrace{\strut\color{black}\onslide<5->{{\heap{[8[6,name=6[3][9,name=9,edge=shadeA]][5]]\draw[gray,very thick,Kite-Kite] (9) to[bend right=45] (6);}}}\onslide<6->{\qquad\raisebox{.5\ht\pinguA}{\tikz[baseline=-.6ex]{\draw[gray,ultra thick,-Kite] (0,0) -- (.75,0);}}~{\heap{[8,name=8[9,name=9,edge=shadeA[3][6]][5]]\draw[gray,very thick,Kite-Kite] (9) to[bend left=45] (8);}}}\onslide<7->{\qquad\raisebox{.5\ht\pinguA}{\tikz[baseline=-.6ex]{\draw[gray,ultra thick,-Kite] (0,0) -- (.75,0);}}~{\heap{[9[8[3][6]][5]]}}}}_{\text{\textcolor{gray}{\LARGE\strut Heapify}}}}$}
\begin{tikzpicture}[overlay,remember picture]
    \onslide<8->{%
        \node[below left=.25cm,yshift=.8cm,scale=.6] (pingu) at (current page.north east) {\rotatebox[origin=c]{180}{\usebox\pinguB}};
        \node[left,scale=.6,text width=6.75cm,align=center,yshift=-.33cm] at (pingu.west) {Ist die unterste Ebene voll, so erschaffen wir einfach eine Neue!};
    }
\end{tikzpicture}
\end{frame}

\subsection{Remove/Get}
\savebox\pinguA{\heap{[9,name=9[8[3][6,name=6]][5]]\draw[gray,ultra thick,-Kite] (6) to[bend right=5] (9);}}
\begin{frame}{Remove\,/\,Get}
\begin{itemize}
    \itemsep8pt
    \item<2-> \vphantom{g}Ersetze oberstes Element durch \say{letztes}
    \item<3-> Anschließend: \textit{heapify}
\end{itemize}
\vspace*{3em}\par
\centering
\downsize{.75\linewidth}{$\color{gray}\onslide<4->{\underbrace{\strut\color{black}\onslide<4->{\usebox\pinguA}\onslide<5->{\qquad\raisebox{.5\ht\pinguA}{\tikz[baseline=-.6ex]{\draw[gray,ultra thick,-Kite] (0,0) to[edge node={node[above=4pt,font=\sbfamily]{$\langle$9$\rangle$}}] (.75,0);}}}}_{\text{\textcolor{gray}{\LARGE\strut Remove}}}}$~$\color{gray}\onslide<5->{\underbrace{~~\strut\color{black}\onslide<5->{{\heap{[6,name=6[8,name=8,edge=shadeA[3][,phantom]][5]]\draw[gray,very thick,Kite-Kite] (8) to[bend left=45] (6);}}}\onslide<6->{\quad\raisebox{.5\ht\pinguA}{\tikz[baseline=-.6ex]{\draw[gray,ultra thick,-Kite] (0,0) -- (.75,0);}}\quad{\heap{[8[6[3][,phantom]][5]]}}}}_{\text{\textcolor{gray}{\LARGE\strut Heapify}}}}$}
\end{frame}

\subsection{Weitere Operationen}
\SidebarCite{dive:heap-cpl}
\SidebarCite{dive:heap-ops}
\begin{frame}{Weitere Operationen}
    \begin{itemize}[<+(1)->]
        \itemsep15pt
        \item Find\,/\,Extract Min\,/\,Max
        \item Replace (one node with another)
        \item Meld\,/\,Join
    \end{itemize}
\end{frame}
\SidebarReset

\section{Arrays}
\subsection{Zusammenhang von Heaps und Arrays}
\savebox\pinguA{\tikz{\pingu[right wing shock,left wing raise,straw hat,pants=paletteD!50!black]}}%
\begin{frame}{Erstaunliche Erkentnisse}
    \onslide<2->{\begin{center}
        \textit{Annahmen}:\smallskip\par
        Heap ist bis auf letzte Ebene komplett gefüllt.\\
        Letzte Ebene füllt sich von links an.\bigskip
    \end{center}}
\begin{columns}[c]
\begin{column}{.55\linewidth}
\footnotesize\begin{itemize}
    \item<5-> Jede gefüllte Ebene \(i\) enthält \(2^i\) Elemente
    \item<6-> Die Nummerierung nach Breitendurchlauf erlaubt Adressierung!
    \item<8-> Das linke Kind von \(n\) ist \(2 \cdot n + 1\), das rechte Kind \(2 \cdot n + 2\)
    \item<9-> Der Elternknoten von \(n\) ist \(\lfloor \frac{n - 1}{2}\rfloor\)
\end{itemize}
\end{column}
\begin{column}{.35\linewidth}
\onslide<3->{\heap[s sep=3em-level*.5em]{[18,name=a[7,name=b[3,name=c[3,name=d][2,name=e]][6,name=f]][-2,name=g[-1,name=h][-2,name=i]]]%
\pgfonlayer{background}
\onslide<4->{\foreach[count=\i] \x in {a,b,c,d} {
        \node[gray,font=\sbfamily] (dn\i) at(\x-|4,0) {\the\numexpr\i-1\relax};
        \draw[lgray!90!white,densely dashed, very thick] (dn\i.west) -- (d.west|-dn\i.west) -- ++(-2.5mm,0);
}}
\onslide<7->{\foreach[count=\i] \x in {a, b, g, c, f, h, i, d, e} {
        \node[paletteA,font=\sbfamily,left=.25mm] at (\x.west) {\the\numexpr\i-1\relax};
}}
\endpgfonlayer}}
\end{column}
\end{columns}
\begin{tikzpicture}[remember picture,overlay]
    \onslide<10->{%
        \node[above right=.25cm,yshift=.33cm,scale=.6] (pingu) at (current page.south west) {\usebox\pinguA};
        \node[above=1mm,xshift=6mm,scale=.75,text width=3.5cm,align=center,font=\footnotesize\sffamily] at(pingu.north) {%
            Hmmmm\ldots\ \only<11->{Dat is ne Array-Nummerierung!}
        };
    }
\end{tikzpicture}
\end{frame}

\savebox\pinguA{\tikz{\pingu[cloak,heart=lgray,eyes angry]}}%
\begin{frame}[fragile]{Ein Heap als Array}
\begin{columns}[c]
\begin{column}{.55\linewidth}
\begin{itemize}
    \item<2-> Heaps sind meist \say{nur} Arrays
    \item<6-> Hilfsroutinen erlauben die angenehme Arbeit:
\begin{uncoverenv}<7->
\lstfs{7}%
\begin{plainjava}
int left(int n) { return 2 * n + 1; }
int right(int n) { return 2 * n + 2; }
int parent(int n) { return (n - 1) / 2; }
\end{plainjava}
\end{uncoverenv}
    \item<8-> Checks schaden natürlich nicht!
\end{itemize}
\end{column}
\begin{column}{.35\linewidth}
\centering\onslide<3->{\heap{[9,name=a[7,name=b[3,name=d][2,name=e]][5,name=c[3,name=f][,phantom]]]%
\pgfonlayer{background}
\onslide<4->{\foreach[count=\i] \x in {a, b, c, d, e, f} {
        \node[paletteA,font=\sbfamily,left=.25mm] at (\x.west) {\the\numexpr\i-1\relax};
}}
\endpgfonlayer}}\bigskip\par
~~~~~\begin{tikzpicture}% urgh - kill me :C
\onslide<5->{%
    \node[lblock,fill=white,very thick,right,outer sep=0pt] (0) at (0,0) {9};
    \foreach[count=\i,remember=\i as \li (initially 0)] \n in {7,5,3,2,3} {
        \node[lblock,fill=white,right,outer sep=0pt,very thick] (\i) at (\li.east) {\n};
    }
    % hacky baby, should have filled
    \draw[lgray,rounded corners=1.55pt,ultra thick] (0.south west) rectangle (5.north east);
    \foreach \i in {0,...,5} {
        \node[below=1mm,paletteA,font=\sbfamily,scale=.6] at (\i.south) {\i};
    }
}%
\end{tikzpicture}%
\end{column}
\end{columns}
\begin{tikzpicture}[remember picture,overlay]
    \onslide<9->{%
        \node[above right=.25cm,xshift=.15cm,yshift=.33cm,scale=.6] (pingu) at (current page.south west) {\usebox\pinguA};
        \node[above=1mm,xshift=3mm,scale=.75,text width=3.5cm,align=center,font=\footnotesize\sffamily] at(pingu.north) {%
            Tipp: Bei Arrays ist meist auch \textit{swap} äußerst hilfreich!%
        };
    }
\end{tikzpicture}
\end{frame}

\subsection{Beispielhaftes Heapify}
\savebox\pinguA{\tikz{\pingu[body=paletteA,eye patch right,bow tie=paletteB]}}
\savebox\pinguB{\tikz{\pingu[body=paletteB,eye patch left,bow tie=paletteA,eyes wink]}}
\savebox\pinguC{\tikz[baseline=-.6ex]{\fill[shadeA] circle[radius=2.15pt];}}
\begin{frame}{Ein absteigendes Beispiel}
\begin{center}
    \onslide<2-|handout:1->{\([\vphantom{\underset{\strut\usebox\pinguC}3}\only<3|handout:1>{\underset{\strut\usebox\pinguC}}3, \only<4-5|handout:2>{\underset{\strut\usebox\pinguC}}9, \only<6|handout:3>{\underset{\strut\usebox\pinguC}}8, \only<7|handout:4>{\underset{\strut\usebox\pinguC}}2, \only<8-11|handout:5-7>{\underset{\strut\usebox\pinguC}}{12}]\)}
\end{center}
\medskip\par
\only<2|handout:0>{\hsStep{[,lblob=shadeD,minimum size=0,inner sep=5pt]}{,,,,}{0}{}{}}%
\only<3|handout:1>{\hsStep{[3,name=a[,lblob=shadeD,edge=shadeD,minimum size=0,inner sep=5pt][,phantom]]\foreach[count=\i] \x in {a} {
    \node[paletteA,font=\sbfamily,left=.25mm] at (\x.west) {\the\numexpr\i-1\relax};
}}{3,,,,}{1}{}{}}%
\only<4|handout:2>{\hsStep{[3,name=3[9,name=9,edge=shadeA][,lblob=shadeD,edge=shadeD,minimum size=0,inner sep=5pt]]\draw[gray,very thick,Kite-Kite] (9) to[bend left,thick] (3);\foreach[count=\i] \x in {3,9} {
    \node[paletteA,font=\sbfamily,left=.25mm,scale=.75] at (\x.west) {\the\numexpr\i-1\relax};
}}{3,9,,,}{2}{1}{2}}%
\only<5|handout:0>{\hsStep{[9,name=9[3,name=3][,lblob=shadeD,edge=shadeD,minimum size=0,inner sep=5pt]]\foreach[count=\i] \x in {9,3} {
    \node[paletteA,font=\sbfamily,left=.25mm,scale=.75] at (\x.west) {\the\numexpr\i-1\relax};
}}{9,3,,,}{2}{}{}}%
\only<6|handout:3>{\hsStep{[9,name=9[3,name=3[,lblob=shadeD,edge=shadeD,minimum size=0,inner sep=5pt][,phantom]][8,name=8]]\foreach[count=\i] \x in {9,3,8} {
    \node[paletteA,font=\sbfamily,left=.25mm,scale=.75] at (\x.west) {\the\numexpr\i-1\relax};
}}{9,3,8,,}{3}{}{}}%
\only<7|handout:4>{\hsStep{[9,name=9[3,name=3[2,name=2][,lblob=shadeD,edge=shadeD,minimum size=0,inner sep=5pt]][8,name=8]]\foreach[count=\i] \x in {9,3,8,2} {
    \node[paletteA,font=\sbfamily,left=.25mm,scale=.75] at (\x.west) {\the\numexpr\i-1\relax};
}}{9,3,8,2,}{4}{}{}}%
\only<8|handout:5>{\hsStep{[9,name=9[3,name=3[2,name=2][12,name=12,edge=shadeA]][8,name=8[,lblob=shadeD,edge=shadeD,minimum size=0,inner sep=5pt][,phantom]]]\draw[gray,very thick,Kite-Kite] (12) to[bend right,thick] (3);\foreach[count=\i] \x in {9,3,8,2,12} {
    \node[paletteA,font=\sbfamily,left=.25mm,scale=.75] at (\x.west) {\the\numexpr\i-1\relax};
}}{9,3,8,2,12}{5}{2}{5}}%
\only<9|handout:6>{\hsStep{[9,name=9[12,name=12,edge=shadeA[2,name=2][3,name=3]][8,name=8[,lblob=shadeD,edge=shadeD,minimum size=0,inner sep=5pt][,phantom]]]\draw[gray,very thick,Kite-Kite] (12) to[bend right,thick] (9);\foreach[count=\i] \x in {9,12,8,2,3} {
    \node[paletteA,font=\sbfamily,left=.25mm,scale=.75] at (\x.west) {\the\numexpr\i-1\relax};
}}{9,12,8,2,3}{5}{1}{2}}%
\only<10-11|handout:7>{\hsStep{[12,name=12[9,name=9[2,name=2][3,name=3]][8,name=8[,lblob=shadeD,edge=shadeD,minimum size=0,inner sep=5pt][,phantom]]]\foreach[count=\i] \x in {12,9,8,2,3} {
    \node[paletteA,font=\sbfamily,left=.25mm,scale=.75] at (\x.west) {\the\numexpr\i-1\relax};
}}{12,9,8,2,3}{5}{}{}}%
\only<12|handout:8>{\hsStep*{[12,lblob=shadeB,minimum width=2.5em,text=black,name=12[9,name=9[2,name=2][3,name=3]][8,name=8[,lblob=shadeD,edge=shadeD,minimum size=0,inner sep=5pt][,phantom]]]\draw[gray,very thick,-Kite] (3) to[bend right=5] (12);\foreach[count=\i] \x in {12,9,8,2,3} {
    \node[paletteA,font=\sbfamily,left=.25mm,scale=.75] at (\x.west) {\the\numexpr\i-1\relax};
}}{12,9,8,2,3}{5}{1}{5}}%
\only<13-14|handout:9>{\hsStep{[3,name=3[9,edge=shadeA,name=9[2,name=2][,lblob=shadeD,edge=shadeD,minimum size=0,inner sep=5pt]][8,edge=shadeA,name=8]]\onslide<14|handout:9>{\draw[gray,very thick,Kite-Kite] (9) to[bend right] (3);}\foreach[count=\i] \x in {3,9,8,2} {
    \node[paletteA,font=\sbfamily,left=.25mm,scale=.75] at (\x.west) {\the\numexpr\i-1\relax};
}}{3,9,8,2,}{4}{}{%
\onslide<14|handout:9>{\draw[gray,very thick,Kite-Kite] (d1.south) to[bend right=20,looseness=1.25] (d2.south);}
}}%
\only<15-|handout:10->{\hsStep{[9,name=9[3,name=3[2,name=2][,lblob=shadeD,edge=shadeD,minimum size=0,inner sep=5pt]][8,,name=8]]\foreach[count=\i] \x in {9,3,8,2} {
    \node[paletteA,font=\sbfamily,left=.25mm,scale=.75] at (\x.west) {\the\numexpr\i-1\relax};
}}{9,3,8,2,}{4}{}{}}%
\begin{tikzpicture}[overlay,remember picture]
    \only<11|handout:7>{%
        \node[below,xshift=-.5cm,yshift=.8cm,scale=.6] (pingu) at (current page.north east) {\rotatebox[origin=c]{135}{\usebox\pinguA}};
        \node[left=-5mm,scale=.6,text width=6.75cm,align=center,yshift=-.66cm] at (pingu.west) {Konstruiert man den Heap nur durch \textit{insert}, verletzt stets max. das neue Element die Heap-Eigenschaft. Weiter ist er schön ausgewogen.};
    }
    \only<12-|handout:8->{%
        \node[below,xshift=-.5cm,yshift=.8cm,scale=.6] (pingu) at (current page.north east) {\rotatebox[origin=c]{135}{\usebox\pinguB}};
        \node[left=-5mm,scale=.6,text width=6.75cm,align=center,yshift=-.66cm] at (pingu.west) {Das Entfernen zur Abwechslung nun mit \say{down-heapify}.\only<13-|handout:9->{\smallskip\par Bei mehreren Konflikten: tausche mit \textit{extremerem} Element.}};
    }
\end{tikzpicture}
\end{frame}

% TODO: percolate stuffies
\section{Abschluss}
\SidebarCite{tsk:search-tree}
\SidebarCite{tsk:data}
\begin{frame}{Zur Übung}
    \begin{itemize}[<+(1)->]
        \itemsep7pt
        \item Visualisiere \textit{insert} \([3, 5, 8, 3, -5, 6]\) (in der Reihenfolge) im \textit{Min}-Heap. Am Besten simultan im Baum und im Array.
        \item Visualisiere nun das Entfernen, bis der Heap leer ist\bigskip
        \item[\scalebox{.5}{\raisebox{3.66pt}{\paletteA{$\blacksquare$}}}] Bei diesen und anderen Datenstrukturen hilft die \textit{praktische} Auseinandersetzung!
    \end{itemize}
\end{frame}
\SidebarReset

\end{document}