\documentclass{bschlangaul-aufgabe}
\bLadePakete{baum}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 3},
  Thematik = {DeleteMin},
  Referenz = 66115-2020-H.T2-TA2-A3,
  RelativerPfad = Examen/66115/2020/09/Thema-2/Teilaufgabe-2/Aufgabe-3.tex,
  ZitatSchluessel = examen:66115:2020:09,
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Halde (Heap)},
  EinzelpruefungsNr = 66115,
  Jahr = 2020,
  Monat = 09,
  ThemaNr = 2,
  TeilaufgabeNr = 2,
  AufgabeNr = 3,
}

Es sei der folgende Min-Heap gegeben:
\index{Halde (Heap)}
\footcite{examen:66115:2020:09}

\begin{center}
\begin{tikzpicture}[b binaer baum]
\Tree
[.10
  [.20
    [.40 ]
    [.25 ]
  ]
  [.15
    [.35 ]
    \edge[blank]; \node[blank]{};
  ]
]
\end{tikzpicture}
\end{center}

\begin{enumerate}

%%
% a)
%%

\item Geben Sie obigen Min-Heap in der Darstellung eines Feldes an,
wobei die Knoten in Level-Order abgelegt sind.

\begin{bAntwort}
\begin{tabular}{llllll}
\bf{0} & \bf{1} & \bf{2} & \bf{3} & \bf{4} & \bf{5} \\
\hline
10     & 20     & 15     & 40     & 25     & 35     \\
\end{tabular}
\end{bAntwort}

%%
% b)
%%

\item Führen Sie wiederholt DeleteMin-Operationen auf dem gegebenen Heap
aus, bis der Heap leer ist. Zeichnen Sie dafür den aktuellen Zustand des
Heaps als Baum und als Feld nach jeder Änderung des Heaps, wobei Sie nur
gültige Bäume zeichnen (d. h. solche die keine Lücken haben).
Dokumentieren Sie, was in den einzelnen Schritten geschieht.

\begin{bAntwort}

%-----------------------------------------------------------------------
%
%-----------------------------------------------------------------------

\bPseudoUeberschrift{Löschen von 10}

\begin{bBaum}{Nach dem Ersetzen von „10“ durch „35“}
\begin{tabular}{lllll}
\bf{0} & \bf{1} & \bf{2} & \bf{3} & \bf{4} \\
\hline
35     & 20     & 15     & 40     & 25     \\
\end{tabular}

\begin{tikzpicture}[b binaer baum]
\Tree
[.35
  [.20
    [.40 ]
    [.25 ]
  ]
  [.15 ]
]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach dem Vertauschen von „35“ und „15“}
\begin{tabular}{lllll}
\bf{0} & \bf{1} & \bf{2} & \bf{3} & \bf{4} \\
\hline
15     & 20     & 35     & 40     & 25     \\
\end{tabular}

\begin{tikzpicture}[b binaer baum]
\Tree
[.15
  [.20
    [.40 ]
    [.25 ]
  ]
  [.35 ]
]
\end{tikzpicture}
\end{bBaum}

%-----------------------------------------------------------------------
%
%-----------------------------------------------------------------------

\bPseudoUeberschrift{Löschen von 15}

\begin{bBaum}{Nach dem Ersetzen von „15“ mit „25“}
\begin{tabular}{llll}
\bf{0} & \bf{1} & \bf{2} & \bf{3} \\
\hline
25     & 20     & 35     & 40     \\
\end{tabular}

\begin{tikzpicture}[b binaer baum]
\Tree
[.25
  [.20
    [.40 ]
    \edge[blank]; \node[blank]{};
  ]
  [.35 ]
]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach dem Vertauschen von „25“ und „20“}
\begin{tabular}{llll}
\bf{0} & \bf{1} & \bf{2} & \bf{3} \\
\hline
20     & 25     & 35     & 40     \\
\end{tabular}

\begin{tikzpicture}[b binaer baum]
\Tree
[.20
  [.25
    [.40 ]
    \edge[blank]; \node[blank]{};
  ]
  [.35 ]
]
\end{tikzpicture}
\end{bBaum}

%-----------------------------------------------------------------------
%
%-----------------------------------------------------------------------

\bPseudoUeberschrift{Löschen von 20}

\begin{bBaum}{Nach dem Vertauschen von „20“ mit „40“}
\begin{tabular}{lll}
\bf{0} & \bf{1} & \bf{2} \\
\hline
40     & 25     & 35     \\
\end{tabular}

\begin{tikzpicture}[b binaer baum]
\Tree
[.40
  [.25 ]
  [.35 ]
]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach dem Vertauschen von „40“ und „25“}
\begin{tabular}{lll}
\bf{0} & \bf{1} & \bf{2} \\
\hline
25     & 40     & 35     \\
\end{tabular}

\begin{tikzpicture}[b binaer baum]
\Tree
[.25
  [.40 ]
  [.35 ]
]
\end{tikzpicture}
\end{bBaum}

%-----------------------------------------------------------------------
%
%-----------------------------------------------------------------------

\bPseudoUeberschrift{Löschen von 25}

\begin{bBaum}{Nach dem Ersetzen von „25“ durch „35“}
\begin{tabular}{ll}
\bf{0} & \bf{1} \\
\hline
35     & 40     \\
\end{tabular}

\begin{tikzpicture}[b binaer baum]
\Tree
[.35
  [.40 ]
  \edge[blank]; \node[blank]{};
]
\end{tikzpicture}
\end{bBaum}

%-----------------------------------------------------------------------
%
%-----------------------------------------------------------------------

\bPseudoUeberschrift{Löschen von 35}

\begin{bBaum}{Nach dem Ersetzen von „35“ mit „40“}
\begin{tabular}{l}
\bf{0} \\
\hline
40     \\
\end{tabular}

\begin{tikzpicture}[b binaer baum]
\Tree
[.40 ]
\end{tikzpicture}
\end{bBaum}

%-----------------------------------------------------------------------
%
%-----------------------------------------------------------------------

\bPseudoUeberschrift{Löschen von 40}

\begin{bBaum}{Nach dem Löschen von „40“}

\end{bBaum}

\end{bAntwort}

\end{enumerate}
\end{document}