Select Git revision
304_Halden.tex
Forked from
Unger, Florian Fedor Fridolin / Datenstrukturen und Algorithm Skript
8 commits behind the upstream repository.
-
Florian Unger authoredFlorian Unger authored
304_Halden.tex 12.09 KiB
\section{Halden (Heaps)}
Halden sind eine Datenstrukturen, welche insbesondere zur Implementierung von priority queues geeignert sind, aber auch
einen worst-case optimalen in-place Sortieralgorithmus bereitstellen. Es gibt zwei Perspektiven auf Halden: Einmal als
Array und einmal als vollständiger Binärbaum:
\begin{definition}[Halde: Arraydefinition]
Eine Halde $\mathcal{H}$ ist ein Array $\mathcal{A}$ von $n$ Elementen mit einer Quasiordnung, welches der folgenden Haldenbedingung genügt:
\[
\mathcal{A}[i] \geq \max\{\mathcal{A}[2i+1], \mathcal{A}[2i+2]\} \text{ für alle } i \in \left\{0,1,\cdots
\floor*{\frac{n}{2}}-1\right\}
\]
\end{definition}
\begin{definition}[Halde: Baumdefinition]
Eine Halde ist ein vollständiger binärer Baum $\mathcal{H}$, welcher in seinen Knoten Elemente mit einer Quasiordnung enthält. Zudem
gilt für Knoten $k \in \mathcal{H}$:
\[
\texttt{data}(k) \geq \max\{\texttt{data}(\texttt{left}(k)), \texttt{data}(\texttt{right}(k))\}.
\]
Dabei ist $\texttt{void\_data}$ kleiner als jedes Element der Quasiordnung.
\end{definition}
Direkt aus der Definition ergibt sich sofort, dass $\mathcal{H}[0]$ beziehungsweise $\texttt{root}(\mathcal{H})$ das Maximum
der Halde ist. Ebenso ist jeder Knoten das Maximum seines Teilbaums. Die Höhe einer Halde ist dabei für $n > 0$
definiert als $h(n) := \floor*{\log_2 n}$. Eine leere Halde hat die Höhe $h(0) = -1$.
\begin{figure}[h]
\centering
\includegraphics[scale=0.15]{bilder/halde_zahlen}
\caption{Eine Halde aus Arrayperspektive. Pfeile zeigen die Beziehung zwischen $i$ und $2i +1$ beziehunsweise
$2i +2$ an.}
\label{fig:halde_array}
\end{figure}
\begin{figure}[H]
\centering
\input{bilder/heap_tree_representation.tex}
\caption{Eine Halde aus Baumperspektive. Kindbeziehungen anstelle der Pfeile aus Abbildung~\ref{fig:halde_array}}
\label{fig:halde_baum}
\end{figure}
\subsection{Verhalden (\texttt{heapify})}
Der Algorithmus $\texttt{heapify}$ repariert eine Fast-Halde, bei dem die Haldenbedingung an genau an der Wurzel
beziehungweise im ersten Element verletzt ist. Wir nehmen also an, dass der linke und rechte Teilbaum von $i$ Halden sind.
Ist das Wurzelelement ein Blatt, so ist die Haldenbedingung immer erfüllt.
Um sonst die Haldenbedingung zu erzwingen, muss das Wurzelelement also mit dem Maximum seiner beiden Kinder getauscht werden.
Dabei wird die Haldenbedingung aber möglicherweise bei betauschten Kindknoten verletzt. Also rufen wir den Algorithmus dort noch einmal auf.
In Pseudocode aus der Array-Perspektive sieht das folgendermaßen aus (Der Pseudocode in Arrayperspektive ist eine
Übungsaufgabe):
\begin{algorithm}[H]
\SetNlSty{texttt}{[}{]}
\caption{\texttt{heapify}($\mathcal{H}$)}
\KwIn{An almost-heap $\mathcal{H}$ with $r := \text{root}(\mathcal{H})$ with above conditions}
\KwOut{A modified $\mathcal{H}$ with its heap structure intact}
$m \leftarrow \max{\texttt{data}(\texttt{left}(r)), \texttt{data}(\texttt{right}(r))}$ \;
\If{$m > \texttt{data}(r)$}{
\eIf{$\texttt{data}(\texttt{left}(r)) = m$}{
$n \leftarrow \texttt{left}(r)$ \;
}{
$n \leftarrow \texttt{right}(r)$ \;
}
$\texttt{swap}(\texttt{data}(n), \texttt{data}(r))$ \;
$\texttt{heapify}(n)$ \;
}
\end{algorithm}
\paragraph{Korrektheit:}
Unter obig beschriebenen Bedingungen repariert der Algorithmus den Wurzelknoten, möglicherweise auf Kosten der
Haldenbedingung auf in einer seiner Kindknoten. Da in dem Fall der Algorithmus rekursiv aufgerufen wird und der
Basisfall (Knoten ist ein Blatt) die Haldenbedingung trivial erfüllt, terminiert der Algorithmus und arbeitet korrekt.
\paragraph{Laufzeit:}
Hier hilft es, die Perspektive des Baums einzunehmen: Wir erkennen, dass der Algorithmus schlimmstenfalls $h =
\log_2(n)$ mal aufgerufen wird. Weniger oft, wenn wir in einer tieferen Ebene starten. Da der Aufruf von
$\texttt{heapify}$ ohne seine rekursiven Unteraufrufe $c \in \mathcal{O}(1)$ dauert, liegt die Laufzeit von
\texttt{heapify} damit in $\mathcal{O}(\log n)$.
\subsection{Aufbau einer Halde aus einem Array/Baum}
Wir können aus einem beliebigen Array (oder vollständigen Binärbaum) eine Halde machen, indem wir, angefangen an den
Blättern bis hin zur Wurzel, immer wieder $\texttt{heapify}$ aufrufen.
\begin{algorithm}[H]
\SetNlSty{texttt}{[}{]}
\caption{\texttt{heapify\_tree}($\mathcal{B}$)}
\KwIn{A complete binary tree $\mathcal{B}$ with $r := \text{root}(\mathcal{B})$}
\KwOut{The same tree but resorted as a heap}
\eIf{$\mathcal{B}$ is a leaf}{
\KwRet $\mathcal{B}$ \;
}{
$\texttt{left}(r) \leftarrow \texttt{heapify\_tree}(\texttt{left}(r))$ \;
$\texttt{right}(r) \leftarrow \texttt{heapify\_tree}(\texttt{right}(r))$ \;
\KwRet $\texttt{heapify}(\mathcal{B})$ \;
}
\end{algorithm}
\paragraph{Korrektheit:}
Dadurch, dass wir von unten nach oben arbeiten, sind Teilbäume bereits Halden. Dadurch sind die Bedingungen von
$\texttt{heapify}$ erfüllt und der Algorithmus arbeitet korrekt.
\paragraph{Laufzeit:}
Die Funktion $\texttt{heapify}$ wird $n$ mal aufgerufen und hat selber einen Aufwand von
$\mathcal{O}(\log n)$. Dadurch ist die Abschätzung für den asymptotischen Aufwand von $\texttt{heapify\_array}$ mit
$\mathcal{O}(n \log n)$ schnell getroffen. Allerdings stellt sich heraus, dass man auch exakter abschätzen kann, da die
Laufzeit von $\texttt{heapify}$ nicht immer der Höhe des kompletten Baumes entspricht. Dadurch erreicht man eine
genauere Abschätzung: Die Laufzeit von $\texttt{heapify\_tree}(\mathcal{A})$ liegt in $Θ(n)$, wobei $n$ die Größe des
Baumes $\mathcal{B}$ ist (Übungsaufgabe).
\subsection{Sortieren mit Halden (Heapsort)}
Mit Hilfe der beiden vorherigen Algorithmen kann man auch einen Sortieralgorithmus konstruieren. Wir starten mit einem
Array/Baum und formen ihn in eine Halde um. An der Wurzel des Baumes bzw dem Anfang des Arrays haben wir dann das
Maximum aller Elemente. Dieses Element gilt als sortiert und wird mit dem letzten Platz des Arrays vertauscht, welcher
nun nicht mehr angefasst wird. Ein erneuter Aufruf von $\texttt{heapify}$ findet wieder das Maximum, wir vertauschen mit
dem vorletzten Feld, etc.
Damit haben wir ein worst-case optimalen in-place Sortieralgorithmus:
\begin{algorithm}[H]
\SetNlSty{texttt}{[}{]}
\caption{\texttt{heapsort}($\mathcal{A}$)}
\KwIn{An array $\mathcal{A}$ of size $n$}
\KwOut{The same Array, but sorted}
$\mathcal{A} \leftarrow \texttt{heapify\_array}(\mathcal{A})$ \;
\For{$i \leftarrow n-1$ \KwTo $1$}{
$\texttt{swap}(\mathcal{A}[i], \mathcal{A}[0])$ \;
$\mathcal{A}[0,\cdots,i] \leftarrow \texttt{heapify}(\mathcal{A}[0,\cdots,i], 0)$ \;
}
\KwRet $\mathcal{A}$
\end{algorithm}
\paragraph{Korrektheit:}
Nach dem initialen Verhalden des Arrays mit $\texttt{heapify\_array}(\mathcal{A})$ ist nun sichergestellt, dass der linke und rechte Teilbaum der Wurzel Halden
sind. Dadurch können wir $\texttt{heapify}$ auf das Wurzelelement aufrufen und haben danach eine garantierte Halde und
damit stets das Maximum an der Spitze. Durch das Vertauschen wird die Haldenbedingung nur an einem Knoten verletzt,
$\texttt{heapify}$ kann also weiter korrekt arbeiten. Da der ``haldifizierte'' Anteil des Arrays mit jedem
Schleifendurchlauf schrumpft und sein Maximum an den sortieren hinteren Teil abgibt, terminiert der Algorithmus und
sortiert das Array.
\paragraph{Laufzeit:}
Es reicht hier obige Abschätzung, dass $\texttt{heapify\_array}$ einen asymptotischen Aufwand von $\mathcal{O}(n \log
n)$ hat. Die Laufzeit wird von den $\frac{n}{2}$ aufrufen von $\texttt{heapify}$, welches $\mathcal{O}(\log n)$ Aufwand
hat, eh dominiert. Also liegt die Laufzeit in $\mathcal{O}(n \log n)$. Damit ist $\texttt{heapsort}$ also worst-case
optimal.
\paragraph{Eigenschaften:}
Der Algorithmus \texttt{heapsort} arbeitet in-place, solang man Zeile [1] in-place hinbekommt (Übungsaufgabe).
Desweiteren ist er worst-case-optimal. Allerdings ist er nicht stabil (Übungsaufgabe) und durch das initiale Verhalden
auch nicht adaptiv.
Desweiteren wird (ungeschickterweise) sehr häufig ein besonders kleines Element an die Spitze getauscht, womit sich auch
die echte Laufzeit, abseits von asymptotischer Analyse, unattraktiv verhält.
\begin{figure}[H]
\centering
\input{bilder/heapsort_1.tex}
\caption{Der Algorithmus \texttt{heapsort} auf den Array $\mathcal{A} = [5,7,3,1,8,2]$. Im ersten Schritt wird
(nacheinander, in dieser Reihenfolge) \texttt{heapify} auf die Blätter mit den Werten $2$, $8$ und $1$ ausgeführt,
was jeweils keinerlei Effekt hat.}
\label{fig:heapsort_1}
\end{figure}
\begin{figure}[H]
\centering
\input{bilder/heapsort_2.tex}
\caption{Der Algorithmus \texttt{heapsort} auf den Array $\mathcal{A} = [5,7,3,1,8,2]$. Im zweiten Schritt wird
\texttt{heapify} auf den Knoten mit dem Wert $3$ ausgeführt, also die Haldenbedingung zu seinem Kind $2$ überprüft.
Da die Haldenbedingung für diesen Unterbaum nicht verletzt ist, passiert weiter nichts.}
\label{fig:heapsort_2}
\end{figure}
\begin{figure}[H]
\centering
\input{bilder/heapsort_3.tex}
\caption{Der Algorithmus \texttt{heapsort} auf den Array $\mathcal{A} = [5,7,3,1,8,2]$. Im dritten Schritt wird
\texttt{heapify} auf den Knoten mit dem Wert $7$ ausgeführt, also die Haldenbedingung zu seinem Unterbaum
überprüft und gegenbenenfalls repariert. Da $8$ größer ist als $7$, werden die beiden Werte getauscht.}
\label{fig:heapsort_3}
\end{figure}
\begin{figure}[H]
\centering
\input{bilder/heapsort_4.tex}
\caption{Der Algorithmus \texttt{heapsort} auf den Array $\mathcal{A} = [5,7,3,1,8,2]$. Im vierten Schritt wird
\texttt{heapify} auf den (getauschten) Knoten mit dem Wert $5$ ausgeführt, also die Haldenbedingung zu seinem Unterbaum
überprüft und gegenbenenfalls repariert. Da $7$ größer ist als $5$, werden die beiden Werte getauscht.}
\label{fig:heapsort_4}
\end{figure}
\begin{figure}[H]
\centering
\input{bilder/heapsort_5.tex}
\caption{Der Algorithmus \texttt{heapsort} auf den Array $\mathcal{A} = [5,7,3,1,8,2]$. Im fünften und letzten Schritt wird
\texttt{heapify} auf den Knoten mit dem Wert $5$ ausgeführt, also die Haldenbedingung zu seinem Unterbaum
überprüft und gegenbenenfalls repariert. Da es sich hierbei um ein Blatt handelt, ist $\texttt{heapify}$ fertig und
damit auch $\texttt{heapify\_tree}$}.
\label{fig:heapsort_5}
\end{figure}
\begin{figure}[H]
\centering
\input{bilder/heapsort_6.tex}
\caption{Der Algorithmus \texttt{heapsort} auf den Array $\mathcal{A} = [5,7,3,1,8,2]$. Im dritten Schritt wird
\texttt{heapify} auf den Knoten mit dem Wert $7$ ausgeführt, also die Haldenbedingung zu seinem Unterbaum
überprüft und gegenbenenfalls repariert. Da $8$ größer ist als $7$, werden die beiden Werte getauscht.}
\label{fig:heapsort_6}
\end{figure}
\subsection{Wartschlange (Priority Queue)*}
Eine der häufigsten Anwendungen von Halden: Warteschlangen mit einer Priorität, bei der immer das dringenste (also das
größte) Element gesucht wird. Da das sofort das erste Arrayelement ist, kommt der Vorteil von Halden voll zum tragen.
Einfügen und Löschen erfolgt mit $\mathcal{O}(\log n)$ Aufwand, wie bei Baumstrukturen üblich.
%
%\begin{algorithm}[H]
% \SetNlSty{texttt}{[}{]}
% \caption{\texttt{heapify}($\mathcal{H}, i$)}
% \KwIn{An almost-heap $\mathcal{H}$ of size $n$ with above conditions and the index $i \in \{0, \cdots, n-1\}$}
% \KwOut{A modified $\mathcal{H}$ with its heap structure intact}
% $l \leftarrow 2i + 1$ \;
% $r \leftarrow 2i + 2$ \;
% $j \leftarrow i$ \;
% \If{$l < n$ and $\mathcal{H}[l] > \mathcal{H}[i]$}{
% $j \leftarrow l$ \;
% }
% \If{$r < n$ and $\mathcal{H}[r] > \mathcal{H}[j]$}{
% $j \leftarrow r$ \;
% }
% \If{$i \neq j$}{
% $\texttt{swap}(\mathcal{H}[i], \mathcal{H}[j])$ \;
% $\mathcal{H} \leftarrow \texttt{heapify}(\mathcal{H},j)$ \;
% }
% \KwRet $\mathcal{H}$
%\end{algorithm}
%
%
%\begin{algorithm}[H]
% \SetNlSty{texttt}{[}{]}
% \caption{\texttt{heapify\_array}($\mathcal{A}$)}
% \KwIn{An array $\mathcal{A}$ of size $n$}
% \KwOut{The same Array but resorted as a heap}
% \For{$i \leftarrow \floor*{\frac{n}{2}}$ \KwTo $0$}{
% $\texttt{heapify}(\mathcal{A}, i)$ \;
% }
% \KwRet $\mathcal{A}$
%\end{algorithm}
%