<commit_before>\subsection{Heapsort}

\begin{frame}{Runtime - Heapsort 1/6}
  \begin{columns}
    \begin{column}{0.5\textwidth}
      Depth of a binary tree:
      \begin{itemize}
        \item
          \textbf{Depth \textit{d}:}
          longest path through the tree
        \item
          Complete binary tree has $n = 2 \cdot d - 1$ nodes
        \item
          Example: $d = 4$\\
          $\Rightarrow n = 2^4 - 1 = 15$
      \end{itemize}
    \end{column}
    \begin{column}{0.5\textwidth}
      \begin{figure}
        \begin{centering}%
          \input{Images/HeapSort/BinaryTree.tikz}%
          \caption{Binary tree with 15 nodes}%
          \label{fig:binary_tree}%
        \end{centering}%
      \end{figure}
    \end{column}
  \end{columns}
\end{frame}

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

\begin{frame}{Runtime - Heapsort 2/6}
  \textbf{Intuitive:}
  \begin{itemize}
    \item
      \textbf{Minsort:}
      To determine the minimum value we have to iterate through all the
      unsorted elements.
    \item
      \textbf{Heapsort:}
      The root-element is always the smallest (min-heap).
      We only need to repair a small part of the full tree after an delete
      operation.
  \end{itemize}
  \textbf{Formal:}
  \begin{itemize}
    \item 
      Let T$(n)$ be the runtime for the \textit{Heapsort}
      algorithm with $n$ elements.
    \item
      On the next pages we will proof $T(n) \leq C \cdot n \, \log_2 n$
  \end{itemize}
\end{frame}<commit_msg>Updated Lecture 2 Chapter 4<commit_after>\subsection{Heapsort}

\begin{frame}{Runtime - Heapsort}
  \textbf{Intuitive:}
  \begin{itemize}
    \item
      \textbf{Minsort:}
      To determine the minimum value we have to iterate through all the
      unsorted elements.
    \item
      \textbf{Heapsort:}
      The root-element is always the smallest (min-heap).
      We only need to repair a small part of the full tree after an delete
      operation.
  \end{itemize}
  \textbf{Formal:}
  \begin{itemize}
    \item 
    Let T$(n)$ be the runtime for the \textit{Heapsort}
    algorithm with $n$ elements.
    \item
    On the next pages we will proof $T(n) \leq C \cdot n \, \log_2 n$
  \end{itemize}
\end{frame}

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

\begin{frame}{Runtime - Heapsort}
  \begin{columns}
    \begin{column}{0.5\textwidth}
      Depth of a binary tree:
      \begin{itemize}
        \item
          \textbf{Depth \textit{d}:}
          longest path through the tree
        \item
          Complete binary tree has $n = 2^d - 1$ nodes
        \item
          Example: $d = 4$\\
          $\Rightarrow n = 2^4 - 1 = 15$
      \end{itemize}
    \end{column}
    \begin{column}{0.5\textwidth}
      \begin{figure}
        \begin{adjustbox}{width=\linewidth}
          \input{Images/HeapSort/BinaryTree.tikz}%
        \end{adjustbox}
        \caption{Binary tree with 15 nodes}%
        \label{fig:binary_tree}%
      \end{figure}
    \end{column}
  \end{columns}
\end{frame}
{'fraction_non_alphanumeric': 0.16677567037279267, 'fraction_numerical': 0.011772400261608895, 'mean_word_length': 1.8038496791934004, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3816406', 'n_tokens_mistral': 976, 'n_tokens_neox': 956, 'n_words': 271}