endprojekt.tex

\section{Endprojekt}


In unserem ersten großen Programme (Einfügesortieren) wir hatten
zwei verschachtelten Schleifen. Eine Schleife geht durch die Elementen
und der andere versucht die richtigen Position zu finden. Diese
innere Schleife im durchschnitt also skaliert mit dem Nummer der Elementen.
Beispielweise für eine total zufällige Eingabe der sortierende Element ist im 
durchschnitt kleiner als die Hälfte der schon sortierten Elementen. Darum 
wir verbrauchen  auch in der inneren Schleife Computerzeit der mit 
dem Nummer von den Elementen ($n$) skaliert. Deswegen ist das Einfügesortieren
ein $n^2$ Algorithmus.

Eine mögliche Entwicklung ist die Haldensortierung. In diesem Projekt werden wir 
diese Algorithmus kennenlernen und implementieren. Die grundsätztliche Datentyp ist 
das \texttt{heap}.

\begin{myexampleblock}{Definition: \texttt{Heap}}
Es ist ein ausgeglichener Binärebaum. Es gibt nur eine Bedingung für die Elementen:
jedes Element muss kleiner sein, als ihre Elter.
\end{myexampleblock} 

In einem \texttt{heap} jede Element hat nur ein Elter, und kann maximal zwei Kinder
haben. Der Strichwort ausgeglichen bedeuted das die Höhe des \texttt{heap}s mit
dem logarithmus von $n$ skaliert muss. In anderem Wörter jede Ebene musst voll sein, vordem
ein neues Ebene benutzt wurde. Bespielweise wir zeigen ein \texttt{heap}
von der $[10,12,6,5,9,13,1,7]$ Reihenfolge auf Abbildung \ref{heapexample}.
\begin{center}
\begin{figure}[!ht]
\begin{center}
% Generated with LaTeXDraw 2.0.8
% Mon Mar 06 15:43:52 CET 2017
% \usepackage[usenames,dvipsnames]{pstricks}
% \usepackage{epsfig}
% \usepackage{pst-grad} % For gradients
% \usepackage{pst-plot} % For axes
\scalebox{0.7} % Change this value to rescale the drawing.
{
\begin{pspicture}(-5,-4)(5,5)
\pscircle[linewidth=0.04,dimen=outer](0,4){.5}
\rput(0, 4){13}
\psline[linewidth=0.04cm](-0.5,3.33333)(-1,2.6666)
\psline[linewidth=0.04cm](-.7,2.9)(-1,2.6666)
\psline[linewidth=0.04cm](-.8,3.2)(-1,2.6666)

\pscircle[linewidth=0.04,dimen=outer](-1.5,2){.5}
\rput(-1.5, 2){10}
\psline[linewidth=0.04cm](0.5,3.33333)(1,2.6666)
\psline[linewidth=0.04cm](.7,2.9)(1,2.6666)
\psline[linewidth=0.04cm](.8,3.2)(1,2.6666)

\pscircle[linewidth=0.04,dimen=outer]( 1.5,2){.5}
\rput( 1.5, 2){12}

\psline[linewidth=0.04cm](-2.3,0.933333)(-1.9,1.466666)
\psline[linewidth=0.04cm](-2.35,1.2)(-2.3,0.933333)
\psline[linewidth=0.04cm](-2.0,1.0)(-2.3,0.933333)

\pscircle[linewidth=0.04,dimen=outer](-2.7,0.4){.5}
\psline[linewidth=0.04cm](-.8,0.933333)(-1.2,1.466666)
\psline[linewidth=0.04cm](-0.75,1.2)(-.8,0.933333)
\psline[linewidth=0.04cm](-1.1,1.0)(-.8,0.933333)

\rput(-2.7, 0.4){7}
\psline[linewidth=0.04cm](2.3,0.933333)(1.9,1.466666)
\psline[linewidth=0.04cm](2.35,1.2)(2.3,0.933333)
\psline[linewidth=0.04cm](2.0,1.0)(2.3,0.933333)

\psline[linewidth=0.04cm](.8,0.933333)(1.2,1.466666)
\psline[linewidth=0.04cm](0.75,1.2)(.8,0.933333)
\psline[linewidth=0.04cm](1.1,1.0)(.8,0.933333)


\pscircle[linewidth=0.04,dimen=outer](-0.8,0.4){.5}
\rput(-0.8, 0.4){9}
\pscircle[linewidth=0.04,dimen=outer](2.7,0.4){.5}
\rput(2.7, .4){1}
\pscircle[linewidth=0.04,dimen=outer](0.8,0.4){.5}
\rput(0.8, 0.4){6}

\psline[linewidth=0.04cm](-3.4,-0.533333333333333)(-3.1,-0.133333333333333)
\psline[linewidth=0.04cm](-3.,-.3)(-3.4,-0.533333333333333)
\psline[linewidth=0.04cm](-3.3,-.2)(-3.4,-0.533333333333333)

\pscircle[linewidth=0.04,dimen=outer](-3.75,-1){.5}
\rput(-3.75, -1){5}


\end{pspicture} 
}
\end{center}
\caption{Ein Heap von der $[10,12,6,5,9,13,1,7]$ Reihenfolge.\label{heapexample}}
\end{figure}
\end{center}
Wie man sieht, grundsätztlich es gibt keine Beziehung zwischen Elementen von der 
gleichen Höhe des Bäumes. Es gibt nur ein Regel: Das Kind muss kleiner sein, als ihres
Elter. Jetzt zeigen wir, wie es im Haldensortierung verwendet wird.
Die Haldensortierung kann mit nur drei Schritten formuliert werden:
\begin{itemize}
\item Stellen wir ein \texttt{heap} aus den Reihenfolge der Zahlen her
\item Nun verschieben wir jeweils das erste Element aus, und das wird mit dem letzten Element 
ersetzt.
\item Das \texttt{heap} Eigenschaft muss wiederhergestellt werden.
\end{itemize}

Das Vorteil des Algorithmus ist dass der Zeit um das \texttt{heap} zu behandeln skaliert
nur mit dem Höhe des Bäumes. Weil der Bäum ausgeglichen ist, ihre Größe skaliert nur mit
$\mathrm{log}(n)$. Wir müssen diese Operationen für alle Elementen erledigen 
deswegen die ganze Zeit skaliert mit $n\mathrm{log}(n)$. Das ist für groß genug $n$ ist
besser als die Einfügesortierung.

Wir verwenden verketteten Liste für die Darstellung des \texttt{heap}-s. Jedes Element muss
ein Zeiger auf ihre Elter, und zwei Zeiger auf ihre rechten und linken Nachfolger haben.
\begin{lstlisting}
typedef struct heap
{
  int val;
  struct heap *left; /* Verweis auf linken Nachfolger  */
  struct heap *right; /* Verweis auf rechten Nachfolger */
  struct heap *parent; /* Verweis auf den Vorgaenger */
} heap;
\end{lstlisting}
Um ein geschloßener Baum zu haben, müssen wir an die folgenden zwei Punkten achten:
\begin{itemize}
\item Der \texttt{parent} Zeiger ist ein \texttt{NULL} Zeiger für die Wurzel des Bäumes. 
\item Die Blätters, die keinen Kinder haben, haben \texttt{NULL} als right und left Zeiger.
\end{itemize}
Jetzt zeigen wir wie mann ein \texttt{heap} aus einem Reihenfolge von Zahlen herstellen kann. Zuerst
müssen wir den ersten freien Platz finden, dann schließen wir das Element hier ein. Danach es kann sein, dass 
das \texttt{heap} Eigenschaft nicht mehr wahr ist. Darum müssen wir das \texttt{heap} Eigenschaft danach immer
überprüfen und wenn es notwendig ist, tauschen wir den aktuellen Wert mit dem Wert von ihrem Elter bis 
das \texttt{heap} Eigenschaft wahr wird.
\begin{figure}[!ht]
\begin{center}
% Generated with LaTeXDraw 2.0.8
% Sun Mar 05 20:17:29 CET 2017
% \usepackage[usenames,dvipsnames]{pstricks}
% \usepackage{epsfig}
% \usepackage{pst-grad} % For gradients
% \usepackage{pst-plot} % For axes
\scalebox{0.7} % Change this value to rescale the drawing.
{
\begin{pspicture}(0,-4)(12.0,3)
\psframe[linewidth=0.04,dimen=outer](3,3)(0.0,2)
\psframe[linewidth=0.04,dimen=outer](11.0,-2.2)(8,-3.2)
\pscustom[linewidth=0.04]
{
\newpath
\moveto(3.1,2.5)
%\lineto(7.5,1.5)
\curveto(3.3,2.5)(3.5,2.4)(4.5,1.7)
}
\rput(4.7, 2.8){\LARGE queue\_put}
\psline[linewidth=0.04cm](4.55,1.9)(4.5,1.7)
\psline[linewidth=0.04cm](4.4,1.6)(4.5,1.7)


\pscustom[linewidth=0.04]
{
\newpath
\moveto(7.2,-1.6)
%\lineto(7.5,1.5)
\curveto(7.2,-1.6)(8,-1.2)(9.5,-2.1)
}
\rput(9, -1.){\LARGE queue\_rem}
\psline[linewidth=0.04cm](9.15,-2.2)(9.5,-2.1)
\psline[linewidth=0.04cm](9.2,-1.8)(9.5,-2.1)


\psframe[linewidth=0.04,dimen=outer](7,1.5)(4,0.5)
\psframe[linewidth=0.04,dimen=outer](7,0.2)(4,-0.8)
\psframe[linewidth=0.04,dimen=outer](7,-1.1)(4,-2.1)
\end{pspicture}
}
\caption{Die Warteschlange\label{warteschlange}}
\end{center}
\end{figure}

Die wichtigsten Schritte sind:
\begin{enumerate}
\item Ersten freien Platz finden
\item Einschließen
\item \texttt{heap} Eigenschaft wiederherstellen
\end{enumerate}
Zuerst möchten wir den ersten freien Platz finden. Lass uns annehmen
das Folgende Beispiel. Eine Familie möchte ein Ticket für ein Konzert kaufen.
Aber es gibt nur eine Karte für Sie, und die Eltern dürfen nicht gehen, weil sie sich 
um ihre Kinder kümmern müssen. Zuerst der Kopf der Familie geht zum Ticketschalter
um das Ticket zu kaufen, und wenn er/sie  kein Kind hat, hat er Glück und
kann zum Konzert gehen. Aber wenn er/sie Kind hat, er/sie ist sehr höflich, und 
gibt die Möchkligkeit für ihre Kind(er) zum Konzert zu gehen. Die Elter möchte 
gute Eltern sein, deswegen ihres Kinder könnten alles tun. In anderen Wörten, er
stellt ihre Kinder zur Warteschlange. Dies wird weitergehen bis der aktuellen Käufer 
keine Kind hat. Dieses Beispiel ist ähnlich wie unseres Problem: den ersten freien 
Platz zu finden. Nachdem Beispiel ist es klar, dass wir eine Datenstrukture ähnlich wie 
die Warteschlange verwenden müssen. In der Abbildung \ref{warteschlange} wir zeigen wie 
die Warteschlange funktioniert. Unter sieht man den Quelltext für die Suchung.


\begin{lstlisting}
queue *q = newqueue(*root); /*Kopf der Familien zur Warteschlange*/
heap *currentheap;
while ((currentheap = queue_rem(&q)) != NULL)
  { // Ein mann kommt aus der Warteschlange
    // Wenn er/sie nicht zwei Kinder hat, bekommt ein neues Kind
    //(Konzert Ticket in unserem Beispiel)
    if (currentheap->left == NULL)
      {
        currentheap->left = newheap(x, currentheap);
        currentheap = currentheap->left;
      }
    else if (currentheap->right == NULL)
      {
        currentheap->right = newheap(x, currentheap);
        currentheap = currentheap->right;
      }
    // Wenn er/sie zwei Kinder hat, stellt ihnen in der
    // Warteschlange und geht aus, die naeschte Kaeufer kommt
    else
      {
        queue_put(currentheap->left, &q);
        queue_put(currentheap->right, &q);
        continue; // Springen zum naechsten Iteration
      }
    break;
  }
\end{lstlisting}
\begin{myexampleblock}{Strichwörter: \texttt{break} und \texttt{continue}}
\begin{itemize}
\item break: Beenden eine Schleife, oder ein Selektion im $switch$.
\item continue: Springen in einer Schleife zu dem nächsten Iteration
\end{itemize}
\end{myexampleblock}


Das großte Unterschied zwischen Stapelspeicher und 
Werteschlange ist, dass im Werteschlange das erste gekommene Element zuerst ausgehen kann. 
So die Umsetzung ist ähnlich wie im Stapelspeicher. Die Untershiede sind
\begin{enumerate}
\item Das Typ der gespeicherte Variable: In diesem Fall ein \texttt{heap}
\item Das \texttt{pop()} Funktion muss das letzte Element ausgeben
\end{enumerate}

Deises Endprojekt wird mehr aus 100 Zeilen Code bestehen.
Um die Durchsichtigkeit unseres Programm zu verteidigen, müssen
wir die verschiedenen Teilen im getrennten Datein schreiben und
Headerdatein verwenden. Beispielweise, das ist ganz ähnlich wie der 
verwendung von \texttt{printf} Standardbibliothekfunktion. In den Haderdatein
wir müssen die Typendefinition und die Funktiondeklarationen speichern.
Wenn wir selbstherstellten Headerdatein verwenden wollen müssen wir durch die
folgende Anweisung beilegen:
\begin{lstlisting}
#include"ownheader.h"
\end{lstlisting}
Standardmäßig in diesem Fall der Kompiler sucht nach der Headerdatei in unserem
Arbeitsbibliothek. Wenn wir den \texttt{<>} Zeichen für beilegen verwenden, sucht
es für den Headerdatei in \texttt{/usr/include}.
Achtung, 
die Typ deklarationen müssen in einem Verschiedenen Datei sein um Querverweise zu vermeiden.
Beispielweise zeigen wir hier das Quelltext und die Headerdatein für die Warteschlange:

\begin{myexampleprogram}{ Programme: \texttt{Die Warteschlange}}	
\begin{lstlisting}{heapqueue.h}
typedef struct heap
{
  int val;
  struct heap *left;
  struct heap *right;
  struct heap *parent;
} heap;
typedef struct queue
{
  struct queue *next;
  heap *element;
} queue;
\end{lstlisting}
\begin{lstlisting}{queue.h}
queue *newqueue(heap *data);
void queue_put(heap *data, queue **first);
heap *queue_rem(queue **first);
void print_queue(queue *first);
void free_queue(queue **first);
\end{lstlisting}

\begin{lstlisting}{queue.c}
#include "heapqueue.h"
#include <stdio.h>
#include <stdlib.h>
// Stellt ein neue queue element her
queue *newqueue(heap *data)
{
  queue *q = (queue *)malloc(sizeof(queue));
  q->element = data;
  q->next = NULL;
  return q;
}
// Schliesst ein neue Element in einem queue ein
void queue_put(heap *data, queue **first)
{
  // existier schon eine Liste
  if ((*first) == NULL)
    { // falls nein
      (*first) = newqueue(data); // erzeuge ein neues Element
      return;
    }
  // falls ja
  queue *temp = newqueue(data); // erzeuge ein neues Element
  temp->next = (*first); // setzte den Zeiger
  (*first) = temp; // temp ist das neue erste Element
}
// Ein Element wird aus dem queue entfernt
heap *queue_rem(queue **first)
{
  queue *temp;
  heap *ret;
  if ((*first) == NULL)
    {
      return NULL;
    }
  if ((*first)->next == NULL)
    { // Besteht nur aus ein Element
      ret = (*first)->element; // Extrahiere das Datum
      free((*first)); // Loesche das erste
      (*first) = NULL;
      return ret; // Gib das datum zurueck
    }
  // Besteht aus mehreren Elementen
  // Suchung fuer das letzte Element
  temp = (*first);
  queue *prev;
  while (temp->next != NULL)
    {
      prev = temp;
      temp = temp->next; // Zeiger auf das naechste Element setzten
    }
  prev->next =
      NULL; // Setzte den Zeiger: Das Ende wird das vorletzte Element sein
  ret = temp->element; // Extrahiere das Datum
  free(temp); // Loeschen das letzte
  return (ret); // Gib das Datum zurueck
}
// Geht ein queue durch
void print_queue(queue *first)
{
  queue *temp = (first);
  if (temp == NULL)
    {
      return;
    }
  while (1)
    {
      printf("%d\t", temp->element->val); // momentanes Datum ausgeben
      temp = temp->next; // Zeiger auf das naechste Element setzten
      if (temp == NULL)
        { // Letztes Element erreicht,
          break; // falls ja, Abbruch
        }
    }
  printf("\n");
}
// Gebt ein queue frei
void free_queue(queue **first)
{
  if ((*first) == NULL)
    return;
  queue *temp = (*first);
  queue *temp2;
  while (1)
    {
      temp2 = temp->next;
      free(temp);
      temp = temp2;
      if (temp == NULL)
        break;
    }
}
\end{lstlisting}
\end{myexampleprogram}
Das Datei \texttt{heapqueue.h} wird die Typdefinitionen enthalten. Wir müssen
diese Headerdatei im Codetext für Warteschlange beilegen, um der Kompiler
den Typ \texttt{heap} und \texttt{queue} verstehen zu können. Natürlich wir müssen 
ein eigenen Headerdatei für die Warteschlange erzeugen, weil die Funktionen 
in einem anderen Datei (\texttt{heap.c}) verwenden werden. Das Unterschied
zwischen Stapelspeicher und Warteschlange sieht man im 
\texttt{queue\_rem} Funktion. In diesem Teil wir suchen für das letzte (freigebende) 
Element in der Warteschlange.

Jetzt wir müssen das \texttt{heap} Eigenschaft überprüfen. Das ist ganz einfach, 
wir ziehen das eingegebene Element oben bis das \texttt{heap} Eigenschaft wahr wird.
Wir zeigen hier das in der Praxis:
\begin{lstlisting}
// Prufen ob es hat Elter und wenn ja ob es goesser ist als ihre Elter
while (current_heap->parent != NULL &&
       current_heap->parent->val < current_heap->val)
  {
    // wenn ja, wir tauschen ihre Werten
    int tmp = current_heap->parent->val;
    current_heap->parent->val = current_heap->val;
    current_heap->val = tmp;
    // Fortsetzen die Pruefung mit dem Elter
    current->heap = current_heap_parent;
  }
\end{lstlisting}
In der zweiten Zeile wir haben scheinbar ein Fehler gemacht. Wir verwenden
den Wert vom Zeiger \texttt{parent} ohne Prüfung. 
Das Geheimnis ist in der
Folge des Ausführung und das \texttt{UND \&\&} Logischefunktion.
Zuerst die Prüfung von dem \texttt{parent} Zeiger wir ausgeführt, und wenn es falls ist, das
ganze Ergebnis wird definitiv falls, und die Ausführung der Ausdrücke beendet. 
So wir werden in diesem Fall den Wert vom Zeiger nicht verwenden.
In der dritten Zeile wir tauschen die Werte um, und danach machen
wir ein Schritt oben mit dem Zeiger. Wir wiederholen es bis
das \texttt{heap} Eigenschaft wahr wird. Jetzt wir können die zwei Teilen
zusammenstellen um ein Code für Einschließen ins \texttt{heap} bekommen.

Wenn wir den Platz gefunden haben, prüfen wir das \texttt{heap} Eigenschaft über
(Zeile 24-26). Dann wir sind fertig, die Warteschlange wird freigegeben und
wir beenden die Schleife mit Hilfe des Strichworts \texttt{break}.
\begin{lstlisting}
void heap_insert(heap** root, int x) {
   //wenn das heap leer war
   if(*root == NULL) {
     *root = newheap(x, NULL);
   }
   else {
     //wenn nicht, suchen wir fuer das ersten freie Platz
     queue* q = newqueue(*root);
     heap* currentheap;

     while((currentheap=queue_rem(&q))!=NULL){

        if(currentheap->left == NULL) {
          currentheap->left  = newheap(x, currentheap);
          currentheap = currentheap->left;
        }
        else if(currentheap->right == NULL) {
          currentheap->right = newheap(x, currentheap);
          currentheap = currentheap->right;
        }
        else {
          queue_put(currentheap->left, &q);
          queue_put(currentheap->right,&q);
          continue;
        }
        //wir haben es gefunden
        //uberpruefung des heap-s Eigenschaft
        while(currentheap->parent != NULL && currentheap->parent->val < currentheap->val) {
           int tmp=current_heap->parent->val;
           current_heap->parent->val=current_heap->val;
           current_heap->val=tmp;
           currentheap = currentheap->parent;
        }
        //wir sind Fertig
        break;
    
     }
     free_queue(&q);
   }
   return;
}
\end{lstlisting}
In diesem Codeteil wir haben der Funktion \texttt{newheap} verwendet. Dieser Funktion
erzeugt ein neues \texttt{heap} Element und hat zwei Eingabeparameter: ein für den neuen 
Wert, und ein Zeiger für ihre Elter. Die aktuellen Quelltext für diesen Funktion 
sieht man unter:
\begin{lstlisting}
heap *newheap( int x, heap *parent){
   heap *ret=(heap *)malloc(sizeof(heap));
   if (ret == NULL){
     printf("Error in memory allocation\n");
     exit(1);
   }
   ret->left=NULL;
   ret->right=NULL;
   ret->parent=parent;
   ret->val=x;
   return ret;
}
\end{lstlisting}
Wenn das \texttt{heap} leer ist, das \texttt{heap\_insert} ist ganz einfach. Wir einschließen ein neues 
Element als die neue Wurzel (Zeile 4, Achtung, den \texttt{parent} Zeiger der Wurzel muss \texttt{NULL} sein). 
Anderfalls wir suchen für den ersten freien Platz
(Sieht die Diskussion oben). Wir schließen die Wurzel in einem Warteschlange, und 
machen eine Schleife bis die Warteschlange leer wird. Wenn wir ein Element
ohne zwei Kinder von der Warteschlange ausgenehmen haben, wird sind fertig, wir
haben den Platz gefunden. Anderfalls wir schließen ihre Kinder in der Warteschlange
ein und springen auf den nächsten Iteration mit Hilfe des Stichwort \texttt{continue}.

In der Entfernung das Prinzip ist die gleiche: Im ersten Schritt wir müssen das letzte Element 
finden, tauschen ihren Wert mit dem Wert von der Wurzel, und zum Ende müssen wir ihn
freigeben. Im zweiten Schritt wir müssen das \texttt{heap} Eigenschaft wiederherstellen.

Die Suchung für das letzte Element ist ähnlich wie im \texttt{heap\_insert} Funktion. Das
unterschied ist dass wir müssen errinern an das Letzte nicht \texttt{NULL} Element. Als 
Eingabe wir haben der Zeiger auf die Wurzel des \texttt{heap}-s. Du kannst die dazuhöringen
Codeteil unter sehen.
\begin{lstlisting}
//Schliesst den Kopf in der Warteschlange
queue* q = newqueue(*root);
heap* previousheap;
heap* currentheap;
//Bis der Warteschlange leer wird
while ((currentheap=queue_rem(&q)) != NULL) {
  if (currentheap->left != NULL)
     queue_put(currentheap->left, &q);
  if (currentheap->right != NULL)
     queue_put(currentheap->right, &q);
  previousheap= currentheap;//Setzt den Zeiger zum letzten Element
}
currentheap = previousheap;//Das wird das letzte Element sein
free_queue(&q);//Wir muessen den queue freigeben
\end{lstlisting}

Grundsätzlich wir tun das Gleiche wie im Einschließen, außer das, dass wir am Ende 
von jeden Iteration den aktuellen Zeiger auf dem \texttt{heap} speicher. Am Ende 
dieser gespeicherte Zeiger wird das letzte Element sein. 

Das Wiederherstellen des \texttt{heap} Eigenschafts ist nicht so trivial als im 
Einschließen. Dafür zeigen wir den Prozess auf Abbildung \ref{loschen}.
Am Anfang wir haben das originalle \texttt{heap} (Teil $a$) und wir werden
den Wert der Wurzel mit dem Wert vom letzten Element umtauschen. Danach
wir zeigen das aktuellen \texttt{heap} im Teil $b$. Natürlich in diesem Fall das \texttt{heap}
Eigenshaft ist nicht mehr wahr. Darum müssen wir den Wert der Wurzel mit der Wert, ihres
größten Kindes umtauschen. Wir zeigen das Ergebnis im Teil $c$. Jetzt
das \texttt{heap} Eigenschaft ist wahr auf den höhsten Ebenen. Nun müssen
wir das \texttt{heap} Eigenschaft also in niedrigen Ebenen wiederherstellen. Das bedeutet
wir müssen das Knote 5 auch mit ihrem größten Kind umtauschen. Dann bekommen wir
das endgültige Ergebnis (Teil $d$).
\begin{figure}[!ht]
\begin{center}
% Generated with LaTeXDraw 2.0.8
% Mon Mar 06 15:43:52 CET 2017
% \usepackage[usenames,dvipsnames]{pstricks}
% \usepackage{epsfig}
% \usepackage{pst-grad} % For gradients
% \usepackage{pst-plot} % For axes
\scalebox{0.5} % Change this value to rescale the drawing.
{
\begin{pspicture}(-5,-4)(5,5)
{\color{red}
\psset
{
    linecolor=red,
    linestyle=dotted,
}
\pscircle[linewidth=0.04,dimen=outer](0,4){.5}
\rput(0, 4){13}
}
\psline[linewidth=0.04cm](-0.5,3.33333)(-1,2.6666)
\psline[linewidth=0.04cm](-.7,2.9)(-1,2.6666)
\psline[linewidth=0.04cm](-.8,3.2)(-1,2.6666)

\pscircle[linewidth=0.04,dimen=outer](-1.5,2){.5}
\rput(-1.5, 2){10}
\psline[linewidth=0.04cm](0.5,3.33333)(1,2.6666)
\psline[linewidth=0.04cm](.7,2.9)(1,2.6666)
\psline[linewidth=0.04cm](.8,3.2)(1,2.6666)

\pscircle[linewidth=0.04,dimen=outer]( 1.5,2){.5}
\rput( 1.5, 2){12}

\psline[linewidth=0.04cm](-2.3,0.933333)(-1.9,1.466666)
\psline[linewidth=0.04cm](-2.35,1.2)(-2.3,0.933333)
\psline[linewidth=0.04cm](-2.0,1.0)(-2.3,0.933333)

\pscircle[linewidth=0.04,dimen=outer](-2.7,0.4){.5}
\psline[linewidth=0.04cm](-.8,0.933333)(-1.2,1.466666)
\psline[linewidth=0.04cm](-0.75,1.2)(-.8,0.933333)
\psline[linewidth=0.04cm](-1.1,1.0)(-.8,0.933333)

\rput(-2.7, 0.4){7}
\psline[linewidth=0.04cm](2.3,0.933333)(1.9,1.466666)
\psline[linewidth=0.04cm](2.35,1.2)(2.3,0.933333)
\psline[linewidth=0.04cm](2.0,1.0)(2.3,0.933333)

\psline[linewidth=0.04cm](.8,0.933333)(1.2,1.466666)
\psline[linewidth=0.04cm](0.75,1.2)(.8,0.933333)
\psline[linewidth=0.04cm](1.1,1.0)(.8,0.933333)


\pscircle[linewidth=0.04,dimen=outer](-0.8,0.4){.5}
\rput(-0.8, 0.4){9}
\pscircle[linewidth=0.04,dimen=outer](2.7,0.4){.5}
\rput(2.7, .4){1}
\pscircle[linewidth=0.04,dimen=outer](0.8,0.4){.5}
\rput(0.8, 0.4){6}

\psline[linewidth=0.04cm](-3.4,-0.533333333333333)(-3.1,-0.133333333333333)
\psline[linewidth=0.04cm](-3.,-.3)(-3.4,-0.533333333333333)
\psline[linewidth=0.04cm](-3.3,-.2)(-3.4,-0.533333333333333)

{\color{red}
\psset{
linecolor=red,
linestyle=dotted,
}
\pscircle[linewidth=0.04,dimen=outer](-3.75,-1){.5}
\rput(-3.75, -1){5}
}
\rput(0,-2.2){\LARGE $(a)$}
\end{pspicture}
}
\quad 
\quad
% \usepackage{pst-plot} % For axes
\scalebox{0.5} % Change this value to rescale the drawing.
{
\begin{pspicture}(-5,-4)(5,5)
{
\color{blue}
\psset{
       linecolor=blue,
       linestyle=dashed,
}
\pscircle[linewidth=0.04,dimen=outer](0,4){.5}
\rput(0, 4){5}
}
\psline[linewidth=0.04cm](-0.5,3.33333)(-1,2.6666)
\psline[linewidth=0.04cm](-.7,2.9)(-1,2.6666)
\psline[linewidth=0.04cm](-.8,3.2)(-1,2.6666)
   
\pscircle[linewidth=0.04,dimen=outer](-1.5,2){.5}
\rput(-1.5, 2){10}
\psline[linewidth=0.04cm](0.5,3.33333)(1,2.6666)
\psline[linewidth=0.04cm](.7,2.9)(1,2.6666)
\psline[linewidth=0.04cm](.8,3.2)(1,2.6666)

{
\color{red}
\psset{
linecolor=red,
linestyle=dotted,
}
\pscircle[linewidth=0.04,dimen=outer]( 1.5,2){.5}
\rput( 1.5, 2){12}
}  
\psline[linewidth=0.04cm](-2.3,0.933333)(-1.9,1.466666)
\psline[linewidth=0.04cm](-2.35,1.2)(-2.3,0.933333)
\psline[linewidth=0.04cm](-2.0,1.0)(-2.3,0.933333)

\pscircle[linewidth=0.04,dimen=outer](-2.7,0.4){.5}
\psline[linewidth=0.04cm](-.8,0.933333)(-1.2,1.466666)
\psline[linewidth=0.04cm](-0.75,1.2)(-.8,0.933333)
\psline[linewidth=0.04cm](-1.1,1.0)(-.8,0.933333)

\rput(-2.7, 0.4){7}
\psline[linewidth=0.04cm](2.3,0.933333)(1.9,1.466666)
\psline[linewidth=0.04cm](2.35,1.2)(2.3,0.933333)
\psline[linewidth=0.04cm](2.0,1.0)(2.3,0.933333)

\psline[linewidth=0.04cm](.8,0.933333)(1.2,1.466666)
\psline[linewidth=0.04cm](0.75,1.2)(.8,0.933333)
\psline[linewidth=0.04cm](1.1,1.0)(.8,0.933333)


\pscircle[linewidth=0.04,dimen=outer](-0.8,0.4){.5}
\rput(-0.8, 0.4){9}
\pscircle[linewidth=0.04,dimen=outer](2.7,0.4){.5}
\rput(2.7, .4){1}
\pscircle[linewidth=0.04,dimen=outer](0.8,0.4){.5}
\rput(0.8, 0.4){6}
\rput(0,-2.2){\LARGE $(b)$}

\end{pspicture}

}
\\
% \usepackage{pst-plot} % For axes
\scalebox{0.5} % Change this value to rescale the drawing.
{
\begin{pspicture}(-5,-4)(5,5)
{\color{blue}
\psset{linecolor=blue,
       linestyle=dashed
}
\pscircle[linewidth=0.04,dimen=outer](0,4){.5}
\rput(0, 4){12}
}
\psline[linewidth=0.04cm](-0.5,3.33333)(-1,2.6666)
\psline[linewidth=0.04cm](-.7,2.9)(-1,2.6666)
\psline[linewidth=0.04cm](-.8,3.2)(-1,2.6666)
   
\pscircle[linewidth=0.04,dimen=outer](-1.5,2){.5}
\rput(-1.5, 2){10}
\psline[linewidth=0.04cm](0.5,3.33333)(1,2.6666)
\psline[linewidth=0.04cm](.7,2.9)(1,2.6666)
\psline[linewidth=0.04cm](.8,3.2)(1,2.6666)

{
\color{blue}
\psset{linecolor=blue,
       linestyle=dashed,
}
\pscircle[linewidth=0.04,dimen=outer]( 1.5,2){.5}
\rput( 1.5, 2){5}
}   
\psline[linewidth=0.04cm](-2.3,0.933333)(-1.9,1.466666)
\psline[linewidth=0.04cm](-2.35,1.2)(-2.3,0.933333)
\psline[linewidth=0.04cm](-2.0,1.0)(-2.3,0.933333)

\pscircle[linewidth=0.04,dimen=outer](-2.7,0.4){.5}
\psline[linewidth=0.04cm](-.8,0.933333)(-1.2,1.466666)
\psline[linewidth=0.04cm](-0.75,1.2)(-.8,0.933333)
\psline[linewidth=0.04cm](-1.1,1.0)(-.8,0.933333)

\rput(-2.7, 0.4){7}
\psline[linewidth=0.04cm](2.3,0.933333)(1.9,1.466666)
\psline[linewidth=0.04cm](2.35,1.2)(2.3,0.933333)
\psline[linewidth=0.04cm](2.0,1.0)(2.3,0.933333)

\psline[linewidth=0.04cm](.8,0.933333)(1.2,1.466666)
\psline[linewidth=0.04cm](0.75,1.2)(.8,0.933333)
\psline[linewidth=0.04cm](1.1,1.0)(.8,0.933333)


\pscircle[linewidth=0.04,dimen=outer](-0.8,0.4){.5}
\rput(-0.8, 0.4){9}
\pscircle[linewidth=0.04,dimen=outer](2.7,0.4){.5}
\rput(2.7, .4){1}
{
\color{red}
\psset{linecolor=red,
       linestyle=dotted,
}
\pscircle[linewidth=0.04,dimen=outer](0.8,0.4){.5}
\rput(0.8, 0.4){6}
}
\rput(0,-2.2){\LARGE $(c)$}

\end{pspicture}
}
\quad
\quad
% \usepackage{pst-plot} % For axes
\scalebox{0.5} % Change this value to rescale the drawing.
{
\begin{pspicture}(-5,-4)(5,5)
\pscircle[linewidth=0.04,dimen=outer](0,4){.5}
\rput(0, 4){12}
\psline[linewidth=0.04cm](-0.5,3.33333)(-1,2.6666)
\psline[linewidth=0.04cm](-.7,2.9)(-1,2.6666)
\psline[linewidth=0.04cm](-.8,3.2)(-1,2.6666)
   
\pscircle[linewidth=0.04,dimen=outer](-1.5,2){.5}
\rput(-1.5, 2){10}
\psline[linewidth=0.04cm](0.5,3.33333)(1,2.6666)
\psline[linewidth=0.04cm](.7,2.9)(1,2.6666)
\psline[linewidth=0.04cm](.8,3.2)(1,2.6666)

{
\color{blue}
\psset{linecolor=blue,
       linestyle=dashed,
}
\pscircle[linewidth=0.04,dimen=outer]( 1.5,2){.5}
\rput( 1.5, 2){6}
}   
\psline[linewidth=0.04cm](-2.3,0.933333)(-1.9,1.466666)
\psline[linewidth=0.04cm](-2.35,1.2)(-2.3,0.933333)
\psline[linewidth=0.04cm](-2.0,1.0)(-2.3,0.933333)

\pscircle[linewidth=0.04,dimen=outer](-2.7,0.4){.5}
\psline[linewidth=0.04cm](-.8,0.933333)(-1.2,1.466666)
\psline[linewidth=0.04cm](-0.75,1.2)(-.8,0.933333)
\psline[linewidth=0.04cm](-1.1,1.0)(-.8,0.933333)

\rput(-2.7, 0.4){7}
\psline[linewidth=0.04cm](2.3,0.933333)(1.9,1.466666)
\psline[linewidth=0.04cm](2.35,1.2)(2.3,0.933333)
\psline[linewidth=0.04cm](2.0,1.0)(2.3,0.933333)

\psline[linewidth=0.04cm](.8,0.933333)(1.2,1.466666)
\psline[linewidth=0.04cm](0.75,1.2)(.8,0.933333)
\psline[linewidth=0.04cm](1.1,1.0)(.8,0.933333)


\pscircle[linewidth=0.04,dimen=outer](-0.8,0.4){.5}
\rput(-0.8, 0.4){9}
\pscircle[linewidth=0.04,dimen=outer](2.7,0.4){.5}
\rput(2.7, .4){1}
{
\color{blue}
\psset{linecolor=blue,
       linestyle=dashed
}
\pscircle[linewidth=0.04,dimen=outer](0.8,0.4){.5}
\rput(0.8, 0.4){5}
}
\rput(0,-2.2){\LARGE $(d)$}

\end{pspicture}
}
\end{center}
\caption{Beispiel für Löschen aus einem $heap$\label{loschen}. Wir haben mit Blau( Geschrichelt )
die Knoten, die im aktuellen Schritt, und mit Rot ( Punktiert ) die Knoten die im 
nächsten Schritt verändert werden.}
\end{figure}


Zusamennfassen wir haben drei Möglichkeiten um das \texttt{heap} Eigenschaft wiederherstellen
(Wir zeigen den Quelltext unter in der Praxis).
\begin{enumerate}
\item Das aktuelle Knote hat kein Kinder: Wir sind fertig (Zeile 4-6).
\item Das aktuelle Knote hat ein Kind: Wir müssen prüfen, ob ihre Wert kleiner ist oder nicht.
Wenn nicht, wir müssen umtauschen. Dann wir sind fertig (Zeile 8-16).
\item Das aktuelle Knote hat zwei Kinder. Wir müssen prüfen ob ihre Kinder sind kleiner oder nicht.
Wenn nicht, wir müssen mit dem größten Kind umtauschen und die Prüfung fortsetzen mit dem größten Kind (Zeile 19-35).
\end{enumerate}
\begin{lstlisting}
int a, b, c;
current_heap = *root;
while(1) {
  if(current_heap->left == NULL) {
    //hat kein Kinder
    break;
  }
  else if(current_heap->right == NULL) {
    //hat nur ein Kinder
    a = current_heap->val;
    b = current_heap->left->val;
    if(a < b) {
      current_heap->val = b;
      current_heap->left->val = a;
    }
    break;
  }//Hat zwei Kinder: Tauschen mit dem groessten
  else {
    a = current_heap->val;
    b = current_heap->left->val;
    c = current_heap->right->val;
    if(a >= b && a >= c) {
      break;
    }
    else if(b > a && b >= c) {
      current_heap->left->val = a;
      current_heap->val = b;
      current_heap = current_heap->left;
    }
    else {
      current_heap->right->val = a;
      current_heap->val = c;
      current_heap = current_heap->right;
    }
  }
\end{lstlisting}
Jetzt sind wir Fertig mit dem \texttt{heap} Teil. In diesem Teil wir müssen den Headerdatei für die Typdefinitionen
(\texttt{heapqueue.h}) und für die Warteschlange
(\texttt{queue.h}) beilegen, weil wir die Typen, bzw. die Funktionen von ihnen verwenden werden.

\begin{myexampleprogram}{Programme: \texttt{Haldensortierung}}
\begin{lstlisting}{heap.h}
void heap_insert(heap **root, int x);
int heap_remove(heap **root);
void print_heap(heap *root);
heap *newheap(int x, heap *parent);
\end{lstlisting}
\begin{lstlisting}{heap.c}
#include "heapqueue.h"
#include "queue.h"
#include <stdio.h>
#include <stdlib.h>
// Stellt ein neue heap her
heap *newheap(int x, heap *parent)
{
  heap *ret = (heap *)malloc(sizeof(heap));
  if (heap == NULL){
    printf("Error in memory allocation\n");
    exit(1);
  }
  ret->left = NULL;
  ret->right = NULL;
  ret->parent = parent;
  ret->val = x;
  return ret;
}
// Schliesst ein Element in einem heap
void heap_insert(heap **root, int x)
{
  if (*root == NULL)
    {
      *root = newheap(x, NULL);
    }
  else
    {
      queue *q = newqueue(*root);
      heap *current_heap;
      // Suchung fuer die Pozition
      while ((current_heap = queue_rem(&q)) != NULL)
        {
          // hat kein Kinder: wir haben gefunden
          if (current_heap->left == NULL)
            {
              current_heap->left = newheap(x, current_heap);
              current_heap = current_heap->left;
            }
          // hat nur ein Kinder : wir haben auch gefunden
          else if (current_heap->right == NULL)
            {
              current_heap->right = newheap(x, current_heap);
              current_heap = current_heap->right;
            }
          // hat zwei Kinder:wir muessen ein neue Iteration machen
          else
            {
              queue_put(current_heap->left, &q);
              queue_put(current_heap->right, &q);
              continue;
            }
          // In diesem Point wir haben den Pozition gefunden, und
          // wir fangen das Heap Eigenschaft wiederherstellen
          while (current_heap->parent != NULL &&
                 current_heap->parent->val < current_heap->val)
            {
              int temp = current_heap->parent->val;
              current_heap->parent->val = current_heap->val;
              current_heap->val = temp;
              current_heap = current_heap->parent;
            }
          // wir sind Fertig
          break;
        }
      // Wir muessen das queue freigeben
      free_queue(&q);
    }
}
// Loescht ein Element aus dem heap
int heap_remove(heap **root)
{
  int ret;
  if (*root != NULL)
    {
      queue *q = newqueue(*root);
      heap *previous_heap;
      heap *current_heap;
      // Suchung fuer das Pozition
      while ((current_heap = queue_rem(&q)) != NULL)
        {
          if (current_heap->left != NULL)
            queue_put(current_heap->left, &q);
          if (current_heap->right != NULL)
            queue_put(current_heap->right, &q);
          previous_heap = current_heap;
        }
      // wir haben es gefunden
      current_heap = previous_heap;
      free_queue(&q);
      // wenn das der Kopf ist wir geben ihre Wert aus
      if (current_heap->parent == NULL)
        {
          ret = current_heap->val;
          free(current_heap);
          *root = NULL;
          return ret;
        }
      else
        {
          // Wenn nicht, wir tauschen ihre Wert mit dem Wert vom Kopf
          ret = (*root)->val;
          (*root)->val = current_heap->val;
          current_heap = current_heap->parent;
          if (current_heap->right != NULL)
            {
              free(current_heap->right);
              current_heap->right = NULL;
            }
          else
            {
              free(current_heap->left);
              current_heap->left = NULL;
            }
          // Und fangen wir das wiederherstellen an.
          int a, b, c;
          current_heap = *root;
          while (1)
            {
              // kein Kinder: wir sind Fertig
              if (current_heap->left == NULL)
                {
                  break;
                }
              // Nur ein Kinder: wir muessen nur einmal Pruefen
              else if (current_heap->right == NULL)
                {
                  a = current_heap->val;
                  b = current_heap->left->val;
                  if (a < b)
                    {
                      current_heap->val = b;
                      current_heap->left->val = a;
                    }
                  break;
                }
              // Zwei Kinder: wir pruefen und machen noch ein Iteration
              else
                {
                  a = current_heap->val;
                  b = current_heap->left->val;
                  c = current_heap->right->val;
                  if (a >= b && a >= c)
                    {
                      break;
                    }
                  else if (b > a && b >= c)
                    {
                      current_heap->left->val = a;
                      current_heap->val = b;
                      current_heap = current_heap->left;
                    }
                  else
                    {
                      current_heap->right->val = a;
                      current_heap->val = c;
                      current_heap = current_heap->right;
                    }
                }
            }
        }
      return ret;
    }
  else
    return 0;
}
void print_heap(heap *root)
{
  if (root != NULL)
    {
      queue *q = newqueue(*root);
      heap *test;
      while ((test = queue_rem(&q)) != NULL)
        {
          if (test->left != NULL)
            queue_put(test->left, &q);
          if (test->right != NULL)
            queue_put(test->right, &q);
          printf("%d ", test->val);
        }
      if (q != NULL)
        free_queue(&q);
      printf("\n");
    }
}
\end{lstlisting}
\end{myexampleprogram}
Im \texttt{main} werden wir das \texttt{heap} verwenden
und darum müssen wir ihres Headerdatei beilegen mit Hilfe
des Strichwort \texttt{\#include\"{}\"{}}. Unter sieht man den
Quelltext in der Praxis.
\begin{myexampleprogram}{Das \texttt{main} Programm}
\begin{lstlisting}{main.c}
#include<stdio.h>
#include<stdlib.h>
#include"heapqueue.h"
#include"heap.h"
int main () {
    heap *root = NULL; //Erzeugen ein Zeiger auf das erste Element
    int i,j;
    heap_insert(&root, 10); //Schliessen wir den Element 10 ein 
    print_heap(root);
    heap_insert(&root, 12);
    print_heap(root);
    heap_insert(&root,  6);
    print_heap(root);
    heap_insert(&root,  5);
    print_heap(root);
    heap_insert(&root,  9);
    print_heap(root);
    heap_insert(&root, 13);
    print_heap(root);
    heap_insert(&root,  1);
    print_heap(root);
    heap_insert(&root,  7);
    print_heap(root);
    printf("Start removing\n");//Fangen wir die Entfernung der Elementen an
    for (i=0; i<8; ++i){
       j=heap_remove(&root);
       printf("Removed item=%d\n", j);
    }
  return 0;
}
\end{lstlisting}
Um diesen Programme zu komplieren, wir müssen zuerst Object code aus allen verschiedenen 
Datein mit Hilfe von \texttt{gcc} erzeugen. Diesen Objekten werden nicht ausführbaren sein. 
Dann wir werden das linker verwenden um ein ausführbaren Datein aus diesen Objekten zu erzeugen.
Hier zeigen wir das in der Praxis:
\\
\begin{verb}
>$  gcc -c queue.c
\end{verb}\\
\begin{verb} 
>$  gcc -c heap.c
\end{verb}\\
\begin{verb}
>$  gcc -c main.c
\end{verb}\\
\begin{verb}
>$  gcc main.o heap.o queue.o -o heapsort.exe
\end{verb}\\
Die Anwendung\\
\begin{verb}
>$ ./heapsort.exe
\end{verb}\\
gibt die folgende Ausgabe:
\begin{verbatim}
10 
12 10 
12 10 6 
12 10 6 5 
12 10 6 5 9 
13 10 12 5 9 6 
13 10 12 5 9 6 1 
13 10 12 7 9 6 1 5 
Start removing
Removed item=13
Removed item=12
Removed item=10
Removed item=9
Removed item=7
Removed item=6
Removed item=5
Removed item=1
\end{verbatim}
\end{myexampleprogram}
%\subsubsection{Formattierte Eingabe und Ausgabe}
%\begin{myexampleblock}{Function definition \texttt{printf}}
%int printf(char * formattierung\_text, $\cdots$);
%\begin{itemize}
%\item Rückgabe Wert: Der Anzahl der ausgedrückten Zeichen
%\item Parameters:
%\begin{enumerate}
%\item formattierung\_text: Eine Zeichenkette, beendet mit dem \'{}\\0\'{} Zeichen, specifiziert wie mann die Daten
%audrücken will
%\end{enumerate}
%\end{itemize}
%\end{myexampleblock}
%\pagebreak