%Teilweise Erzeugt mit dem LaTeX-Generator: http://latex.sehnot.de

%Schriftgröße, Layout, Papierformat, Art des Dokumentes
\documentclass[10pt,oneside,a4paper]{scrartcl}

%Einstellungen der Seitenränder
\usepackage[left=2cm,right=2cm,top=1.5cm,bottom=1.5cm,includeheadfoot]{geometry}

%neue Rechtschreibung
\usepackage[ngerman]{babel}

%Umlaute ermöglichen
\usepackage[utf8]{inputenc}

%Gesamtseitenzahl
\usepackage{lastpage}

% Kopf- und Fußzeile
\usepackage[automark]{scrpage2}

%Quellcode-Listings
\usepackage{listings}

%Hyperlinks
\usepackage{hyperref}

%Baumdiagramme
\usepackage{qtree}

%Kopfzeile
\ihead{Java}
\chead{}
\ohead{http://kohnlehome.de/informatik/heapsort.pdf}
\setheadsepline{0.5pt}

%Fußzeile
\setfootsepline{0.5pt}
\ifoot{Franz Kohnle}
\cfoot{Seite \thepage\ von  \pageref{LastPage}}
\ofoot{\today}

\pagestyle{scrheadings}

\begin{document}

% Überschrift 
\begin{center}
\LARGE % Schriftgröße
\bfseries % Fettdruck
\sffamily % Serifenlose Schrift
Heapsort
\end{center}

\section*{Heap}
Binärer Baum. Alle Väter sind kleiner als ihre Kinder.
\section*{Heapsort-Algorithmus}
\begin{verbatim}
Wiederhole n-mal
    1. Forme Baum zu Heap um:
        von unten nach oben, von rechts nach links:
        Vater tauscht mit kleinerem Sohn
    2. Entferne Wurzel (ist kleinstes Element),
       letztes Element wird neue Wurzel
\end{verbatim}



\section*{Beispiel}
Sortiere die Zahlenfolge 42, 25, 5, 23, 73, 37, 13

\subsection*{1. Heap mit 7 Knoten bilden}
Noch keine Zahlen sortiert\\


\begin{tabular}{|p{3.7cm}|p{3.7cm}|p{3.7cm}|p{3.7cm}|}
\hline
1. & 2. & 3. & 4. Baum ist Heap\\

\Tree [.{42}
          [.\textbf{25} [.\textbf{23} ] 
              [.73 ]] 
          [.5 [.37 ]
              [.13 ]]] & 
              
\Tree [.{\textbf{42}}
          [.23 [.25 ] 
              [.73 ]] 
          [.\textbf{5} [.37 ]
              [.13 ]]] &

\Tree [.{5}
          [.23 [.25 ] 
              [.73 ]] 
          [.\textbf{42} [.37 ]
              [.\textbf{13} ]]] &              
               
\Tree [.{\textit{5}}
          [.23 [.25 ] 
              [.73 ]] 
          [.13 [.37 ]
              [.\textit{42} ]]]\\ \hline 

\end{tabular} 

\subsection*{2. Heap mit 6 Knoten bilden}
Bereits sortierte Zahl: 5\\

\begin{tabular}{|p{3.7cm}|p{3.7cm}|p{3.7cm}|}
\hline
5. & 6. & 7. Baum ist Heap\\


\Tree [.{\textbf{42}}
          [.23 [.25 ] 
              [.73 ]] 
          [.\textbf{13} [.37 ]
              ]] & 
           
\Tree [.{13}
          [.23 [.25 ] 
              [.73 ]] 
          [.\textbf{42} [.\textbf{37} ]
              ]] &
           
\Tree [.{\textit{13}}
          [.23 [.25 ] 
              [.73 ]] 
          [.37 [.\textit{42} ]
              ]]
\\ \hline 
\end{tabular} 


\subsection*{3. Heap mit 5 Knoten bilden}
Bereits sortierte Zahlen: 5, 13\\

\begin{tabular}{|p{3.7cm}|p{3.7cm}|p{3.7cm}|}
\hline
8. & 9. & 10. Baum ist Heap\\
 
\Tree [.{\textbf{42}}
          [.\textbf{23} [.25 ] 
              [.73 ]] 
          [.37 ]] & 
              
\Tree [.{23}
          [.\textbf{42} [.\textbf{25} ] 
              [.73 ]] 
          [.37 ]] &

\Tree [.{\textit{23}}
          [.25 [.42 ] 
              [.\textit{73} ]] 
          [.37 ]]              

\\ \hline 
\end{tabular} 

\newpage

\subsection*{4. Heap mit 4 Knoten bilden}
Bereits sortierte Zahlen: 5, 13, 23\\

\begin{tabular}{|p{3.7cm}|p{3.7cm}|p{3.7cm}|}
\hline
11. & 12. & 13. Baum ist Heap\\
 

\Tree [.{\textbf{73}}
          [.\textbf{25} [.42 ] 
              ] 
          [.37 ]] & 
           
\Tree [.{25}
          [.\textbf{73} [.\textbf{42} ] 
              ] 
          [.37 ]] &
            
\Tree [.{\textit{25}}
          [.42 [.\textit{73} ] 
              ] 
          [.37 ]] 
\\ \hline 
\end{tabular} 


\subsection*{5. Heap mit 3 Knoten bilden}
Bereits sortierte Zahlen: 5, 13, 23, 25\\

\begin{tabular}{|p{3.7cm}|p{3.7cm}|}
\hline
14. & 15. Baum ist Heap\\ 

\Tree [.{\textbf{73}}
          [.42 ] 
          [.\textbf{37} ]] & 
             
\Tree [.{\textit{37}}
          [.42 ] 
          [.\textit{73} ]]   
\\ \hline
\end{tabular} 


\subsection*{6. Heap mit 2 Knoten bilden}
Bereits sortierte Zahlen: 5, 13, 23, 25, 37\\

\begin{tabular}{|p{3.7cm}|p{3.7cm}|}
\hline
16. & 17. Baum ist Heap\\ 

\Tree [.{\textbf{73}}
          [.\textbf{42} ] 
          ] & 

\Tree [.{\textit{42}}
          [.\textit{73} ] 
          ]           
\\ \hline
\end{tabular} 


\subsection*{7. Heap mit 1 Knoten bilden}
Bereits sortierte Zahlen: 5, 13, 23, 25, 37, 42\\

\begin{tabular}{|p{3.7cm}|}
\hline
18. Baum ist Heap\\ 

\Tree [.{\textit{73}} ] 
\\ \hline 
\end{tabular} 

\subsection*{8. Zahlen sind sortiert}
5, 13, 23, 25, 37, 42, 73

\end{document}
