\documentclass{paper}

\setlength {\parindent} {0 pt}
\setlength {\parskip} {1.5 ex plus 0.5 ex minus 0.2 ex}

\usepackage{ngerman}
\usepackage{fullpage}
\usepackage{eurosym}
\usepackage {amssymb}
\usepackage {amsmath}
\usepackage {amsthm}
\usepackage {graphicx}
%\usepackage {wasysym}
\usepackage [usenames] {color}

\usepackage {enumerate}
\usepackage {cite}
\usepackage{float}
\usepackage {xspace}


\floatstyle{ruled}
\newfloat{algorithm}{thp}{alg}
\floatname{algorithm}{Algorithm}


%\usepackage {hyperref}

\newcommand {\mathset} [1] {\ensuremath {\mathbb {#1}}}
\newcommand {\R} {\mathset {R}}
\newcommand {\Q} {\mathset {Q}}
\newcommand {\Z} {\mathset {Z}}
\newcommand {\EX} {\mathbf {E}}
\newcommand {\script} [1] {\ensuremath {\mathcal {#1}}}
\newcommand {\etal} {\textit {et al.}}
\newcommand {\eps} {\varepsilon}
\newcommand {\eqdef} {:=}
\newcommand {\boruvka}{Bor\r{u}vka}
\newcommand {\wspd}{\texttt{wspd}}
\DeclareMathOperator {\emst}{emst}
\DeclareMathOperator {\conv}{CH}
\DeclareMathOperator {\argmin}{argmin}
\DeclareMathOperator {\DT}{DT}
\DeclareMathOperator {\UC}{UC}
\DeclareMathOperator {\LC}{LC}

\newtheorem {theorem} {Satz}
\newtheorem {inv}[theorem] {Invariante}
\newtheorem {fact}[theorem] {Fakt}
\newtheorem {problem}[theorem] {Problem}
\newtheorem {obs}[theorem] {Beobachtung}
\newtheorem {lemma}[theorem] {Lemma}
\newtheorem {observation}[theorem] {Observation}
\newtheorem {corollary}[theorem] {Corollary}
\newtheorem {claim}[theorem] {Claim}
\newtheorem {definition}[theorem] {Definition}


\title{Quake Heaps --- Erdbebenhaufen}
\author{Wolfgang Mulzer}

\begin{document}
\maketitle

\section{Priorit\"atswarteschlangen}

Sei $X$ eine Menge von \emph{Elementen} und
$K$ eine total geordnete Menge von \emph{Schl\"usseln}. 
Eine \emph{Priorit\"atswarteschlange} speichert eine Menge 
$S \subseteq X \times K$ und unterst\"utzt die folgenden Operationen:
\begin{itemize}
  \item \texttt{insert}$(x,k)$: F\"uge das Element $x$ mit Schl\"ussel $k$ zu $S$ 
     hinzu.
  \item \texttt{decrease-key}$(x,k)$: Verringere den Schl\"ussel f\"ur $x$ zu
     $k$. Dabei muss $x$ in $S$ vorhanden sein, und der alte Schl\"ussel
     f\"ur $x$ muss gr\"o\ss{}er als $k$ sein.
  \item \texttt{delete-min}$()$: Finde das Element in $S$ mit dem 
    kleinsten Schl\"ussel, entferne es
     und gib es zur\"uck.
\end{itemize}
Timothy Chans Quake Heaps implementieren den ADT
Priorit\"atswarteschlange. 
Sie erreichen konstante amortisierte Laufzeit f\"ur \texttt{insert}
und \texttt{decrease-key} sowie $O(\log n)$ amortisierte Laufzeit f\"ur
\texttt{delete-min}.

\section{Turnierb\"aume}


\subsection{Definition}

Quake Heaps speichern die Elemente in \emph{Turnierb\"aumen}. 
Ein Turnierbaum ist ein gewurzelter Baum mit den folgenden Eigenschaften
(siehe auch Abbildung~\ref{fig:turnierb}).
\begin{enumerate}
  \item Alle Elemente und Schl\"ussel sind in den Bl\"attern gespeichert.
  \item Alle Bl\"atter haben die gleiche Tiefe, d.h., alle Pfade von der
     Wurzel zu Bl\"attern sind gleich lang.
  \item Alle inneren Knoten haben 1 oder 2 Kinder.
  \item Jeder innere Knoten verweist auf einen Schl\"ussel, 
    das Minimum der Schl\"ussel seiner Kinder.
  \item Jedes Blatt $v$ enth\"alt einen Verweis auf den h\"ochsten Knoten, 
    der auf den  Schl\"ussel in $v$ verweist.
\end{enumerate}

\begin{figure}[ht]
\begin{center}
\includegraphics[scale=1.5]{turnierb}
\end{center}
\caption{Ein Turnierbaum. Alle Bl\"atter haben die gleiche Tiefe.
Jeder innere Knoten hat h\"ochstens 2 Kinder und speichert
das Minimum seiner Kinder.}\label{fig:turnierb}
\end{figure}
\subsection{\texttt{Link} und \texttt{Cut}}
  Turnierb\"aume unterst\"utzen zwei Operationen:
  \texttt{link} und \texttt{cut} (siehe Abbildung~\ref{fig:linkcut}).
  \begin{figure}[ht]
    \begin{center}
       \includegraphics{linkcut}
     \end{center}
     \caption{Die Operationen \texttt{link} und \texttt{cut}.
     \texttt{link} vereinigt zwei Turnierb\"aume gleicher H\"ohe zu 
     einem neuen Turnierbaum. \texttt{cut} schneidet einen Turnierbaumen
     in zwei Teile.}
     \label{fig:linkcut}
   \end{figure}

\paragraph{\texttt{link}.}
  Die Operation \texttt{link} erh\"alt zwei Turnierb\"aume
  $T_1$ und $T_2$ gleicher H\"ohe $h$ und vereinigt sie zu einen Turnierbaum
  der H\"ohe $h+1$. Sie erzeugt eine neue Wurzel $r$, die auf das Minimum
  der Schl\"ussel in den Wurzeln von $T_1$ und $T_2$ verweist, und
  macht $T_1$ und  $T_2$ zu Kindern von $r$.  Dies ergibt einen
  g\"ultigen Turnierbaum, und alle Zeiger k\"onnen in $O(1)$ Zeit
  aktualisiert werden. Folglich l\"auft \texttt{link} in konstanter Zeit.

\paragraph{\texttt{cut}.} Die Operation \texttt{cut} erh\"alt einen Zeiger
  auf einen Knoten $v$, so dass sich der Schl\"ussel in $v$ 
  von dem Schl\"ussel in $v$'s Elternknoten unterscheidet.
  Die Operation l\"oscht die Kante zwischen $v$ und seinem Eltern\-knoten.
  Dadurch enstehen zwei g\"ultige Turnierb\"aume, und die Laufzeit ist $O(1)$. 

\section{Operationen}

Ein Quake Heap besteht aus einer Liste von Turnierb\"aumen.
Die Operationen sind wie folgt implementiert.

\subsection{\texttt{insert}}

Die Operation \texttt{insert}$(x,k)$ erzeugt einen neuen Turnierbaum, 
der nur aus einem Blatt mit Eintrag $(x,k)$ besteht, und f\"ugt ihn
in die Liste ein. Dies ben\"otigt $O(1)$ Zeit.

\begin{figure}
\begin{center}
\includegraphics[scale=1.5]{qheap}
\end{center}
\caption{Ein Quake Heap mit vier Turnierb\"aumen. Es gibt zwei
B\"aume der H\"ohe $0$, einen Baum der H\"ohe 2 und einen Baum der
H\"ohe 4. Ebene 0 hat 11 Knoten, Ebene 1 hat 6 Knoten, Ebene 2
hat 4 Knoten, Ebene 3 hat 2 Knoten, und Ebene 4 hat 1 Knoten.
Die Invariante ist auf allen Ebenen erf\"ullt.}
\label{fig:qheap}
\end{figure}


\subsection{\texttt{decrease-key}}

Die Operation \texttt{decrease-key}$(x,k)$ erh\"alt einen Verweis
auf das Blatt, welches das Element $x$ speichert. Dieser
Verweis wird von \texttt{insert} zur\"uckgeliefert, und er erspart 
uns die Suche nach $x$ im Quake Heap. 

Wir finden zuerst den 
h\"ochsten Knoten $v$, der auf den Schl\"ussel f\"ur $x$ verweist. Dies geht
in konstanter Zeit mit Hilfe des Verweises im Blatt.
Wenn $v$ keine Wurzel ist, f\"uhren wir \texttt{cut}$(v)$ aus. Dies ergibt
einen Baum, in dem der Schl\"ussel f\"ur $x$ minimal ist.
Daher k\"onnen wir den Schl\"ussel f\"ur $x$ 
auf $k$ verringern, ohne die Turnierbaum-Eigenschaften zu verletzen. 
Die Laufzeit ist konstant, da die inneren Knoten nur Verweise auf die
Schl\"ussel speichern und wir daher den Schl\"ussel nur an einer
Stelle \"andern m\"ussen.

\subsection{\texttt{delete-min}}

Um \texttt{delete-min} effizient zu implementieren, ben\"otigen wir
einige zus\"atzliche Informationen in unserem Quake Heap. Neben den
Turnierb\"aumen speichern wir zwei weitere Arrays.
\begin{itemize}
  \item \emph{Das Array} \texttt{T}. Der Eintrag \texttt{T[$i$]} speichert
     eine Liste von allen B\"aumen mit H\"ohe $i$.
  \item \emph{Das Array} \texttt{n}. Der Eintrag \texttt{n[$i$]} speichert
     die Anzahl der Knoten mit H\"ohe $i$.
\end{itemize}
Die Arrays \texttt{T} und \texttt{n} k\"onnen mit konstantem Zusatzaufwand 
aktualisiert werden.
Au\ss{}erdem muss vor und nach jeder Operation die folgenden Invariante 
gelten:
\begin{inv}\label{inv:numbers}
F\"ur alle $i \geq 0$ gilt 
$\textup{\texttt{n}}[i+1] \leq \frac{3}{4}\cdot\textup{\texttt{n}}[i]$.
\end{inv}
Die n\"achsten beiden Fakten folgen nun unmittelbar.
\begin{fact}\label{fact:height}
Invariante~\ref{inv:numbers} impliziert, dass alle Knoten H\"ohe
$O(\log n)$ haben.
\end{fact}
\begin{fact}
Die Operationen  
\textup{\texttt{insert}} und \textup{\texttt{decrease-key}} erhalten 
Invariante~\ref{inv:numbers}.
\end{fact}
Nun k\"onnen wir \texttt{delete-min} beschreiben.
Es besteht aus den folgenden vier Schritten:
\begin{enumerate}
\item \textbf{Minimum finden}. Gehe alle Wurzeln durch
  und finde das Element $x$ mit minimalem Schl\"ussel.
\item \textbf{Minimum l\"oschen}. L\"osche den Pfad, der $x$ entspricht.
  Dies erzeugt gegebenenfalls neue B\"aume.
\item \textbf{Konsolidieren}. Stelle sicher,
  dass alle B\"aume verschiedene H\"ohen haben. Dies geschieht 
  wie folgt:
  \begin{enumerate}
    \item \texttt{for $i$ := $0$ to $O(\log n)$ do}
    \item \qquad \texttt{while T[$i$].size $\geq 2$ do}
    \item \qquad \qquad L\"osche zwei B\"aume $T_1$, $T_2$ aus \texttt{T[$i$]}.
    \item \qquad \qquad $T^* \leftarrow \texttt{link}(T_1, T_2)$.
    \item \qquad \qquad $\texttt{T}[i+1] \leftarrow \texttt{T}[i+1]\,\texttt{++}\, T^*$.
  \end{enumerate}
\item \textbf{Erdbeben}. Stelle sicher, dass
  Invariante~\ref{inv:numbers} erf\"ullt ist. Gehe dazu alle Ebenen
  durch und finde die niedrigste Ebene $i$,
  f\"ur die 
  $\texttt{n}[i+1] > \frac{3}{4}\cdot \texttt{n}[i]$ ist (d.h.,
  Ebene $i$ verletzt Invariante~\ref{inv:numbers}). 
  Falls die Ebene $i$ existiert, l\"osche alle Knoten mit 
  H\"ohe gr\"o\ss{}er als $i$. Ansonsten tue nichts. 
\end{enumerate}
Zur Analyse von \texttt{delete-min} ben\"otigen wir zwei Lemmas.
\begin{lemma}\label{lem:additional_height}
Der Konsolidierungsschritt erzeugt h\"ochstens $O(\log n)$ neue
Ebenen.
\end{lemma}

\begin{proof}[Beweis]
Sei $h$ die h\"ochste nichtleere Ebene vor der
Konsolidierung. 
Betrachte alle Knoten mit H\"ohe gr\"o\ss{}er $h$, die beim
Konsolidieren entstehen. Da \texttt{link} nur Knoten mit zwei Kindern
erzeugt, ist jeder solche Knoten in einem perfekten bin\"aren Baum mit
h\"ochstens $n$ Bl\"attern enthalten (hierbei betrachten wir die Knoten mit
H\"ohe $h$ als die Bl\"atter). 
Folglich gibt es h\"ochstens $O(\log n)$ zus\"atzliche
Ebenen.
\end{proof}

\begin{lemma}\label{lem:delete-min}
Sei $T_0$ die Anzahl der B\"aume vor 
\textup{\texttt{delete-min}}.
Die Zeit f\"ur \textup{\texttt{delete-min}} ist $O(\log n + T_0 + D)$,
wobei $D$ die Anzahl der gel\"oschten Knoten bezeichnet.
\end{lemma}
\begin{proof}[Beweis]
Wir brauchen $O(T_0)$ Zeit, um das Minimum zu finden.
Wegen Fakt~\ref{fact:height} ben\"otigen wir $O(\log n)$ Schritte
zum L\"oschen des Minimums.
Der Konsolidierungsschritt 
ben\"otigt $O(\log n)$ Zeit f\"ur die \texttt{for}-Schleife,
plus die Zeit f\"ur die 
\texttt{link}-Operationen. Ein \texttt{link} braucht 
konstante Zeit, und bei jedem Link verringert sich die Anzahl der B\"aume um
eins. Da es vor dem Konsolidieren h\"ochstens $T_0 + O(\log n)$ B\"aume gibt
(im zweiten Schritt entstehen ggf.~$O(\log n)$ neue B\"aume), ist
die Zeit zum Konsolidieren $O(T_0 + \log n)$. Die Laufzeit f\"ur
das Erdbeben ist $O(\log n)$, um die Ebene $i$ zu suchen (wegen 
Lemma~\ref{lem:additional_height}), plus  $O(D)$, um die Knoten zu
l\"oschen. 
Insgesamt ergibt sich also eine Laufzeit von
$O(\log n + T_0 + D)$.
\end{proof}

\section{Analyse}

Wir wollen nun die folgende Aussage beweisen:
\begin{theorem}\label{thm:runtime}
Jede Operationsfolge mit $i$ \textup{\texttt{insert}}s, $d$ 
\textup{\texttt{decrease-key}}s und $e$ \textup{\texttt{delete-min}}s
ben\"otigt $O(i + d + e\log n)$ Zeit. Dabei ist
$n$ die maximale Anzahl von Elementen, die im Quake Heap
gespeichert sind. Das hei\ss{}t, 
\textup{\texttt{insert}} und \textup{\texttt{decrease-key}} haben
amortisierte Laufzeit $O(1)$, \textup{\texttt{delete-min}}
hat amortisierte Laufzeit $O(\log n)$.
\end{theorem}
Die Idee ist, dass ein
\texttt{delete-min} nur dann lange dauern kann, wenn viele
\texttt{insert}s oder \texttt{decrease-key}s vorausgegangen sind.
Wir k\"onnen somit diese Zeit den vorherigen Operationen in Rechnung
stellen. Es gibt verschiedene Methoden, um diese Umverteilung der 
Kosten zu formalisieren. 
Wir beschreiben die Analyse mit der \emph{Buchhaltermethode}.
In der \"Ubung wird die \emph{Potentialmethode} diskutiert.

Wir stellen uns vor, dass es f\"ur unseren
Quake Heap die folgenden drei Konten gibt.
\begin{itemize}
\item Das \emph{Knotenkonto} enth\"alt 1 \euro{} f\"ur jeden Knoten im Quake
  Heap.
\item Das \emph{Baumkonto} enth\"alt 2 \euro{} f\"ur jeden Baum im Quake
  Heap.
\item Das \emph{Einzelkinderkonto} enth\"alt 4 \euro{} f\"ur jeden inneren
  Knoten, der nur ein Kind besitzt.
\end{itemize}
Die obigen Eigenschaften der Konten bezeichnen wir als 
\emph{Konteninvariante}.
Zu Beginn gibt es keine Knoten und alle Konten sind leer.
Wir zeigen folgendes:
Angenommen, wir zahlen $O(1)$ \euro{} f\"ur jedes \texttt{insert} und
\texttt{decrease-key} und $O(\log n)$ \euro{} f\"ur jedes \texttt{delete-min}.
Dann haben wir gen\"ugend Geld, um  die tats\"achlichen Kosten
der Operationen zu bezahlen, ohne die Konteninvariante zu
verletzen. Satz~\ref{thm:runtime}  folgt dann sofort.

\paragraph{\texttt{insert}.} Die realen Kosten sind $O(1)$.
  Wir erzeugen einen neuen Knoten und einen neuen Baum,
  m\"ussen also 1 \euro{} in das Knotenkonto und 2 \euro{} in
  das Baumkonto zahlen. Insgesamt sind $O(1)$ \euro{} zu bezahlen.

\paragraph{\texttt{decrease-key}.} Die realen Kosten sind $O(1)$.
  Ggf.~entstehen ein neuer Baum und ein neues 
  Einzelkind, also sind bis zu 2 \euro{} auf
  das Baumkonto und 4 \euro{} auf das Einzelkinderkonto zu zahlen. 
  Insgesamt also $O(1)$ \euro{}.

\paragraph{\texttt{delete-min}.} Laut Lemma~\ref{lem:delete-min}
  sind die realen Kosten $O(\log n + T_0 + D)$, wobei
  $T_0$ die anf\"angliche Anzahl der B\"aume ist und $D$ die Anzahl
  der gel\"oschten Knoten. Wir beschreiben nun die notwendige Buchf\"uhrung.
  \begin{enumerate}
    \item Hebe $T_0$ \euro{} vom Baumkonto ab, um die $O(T_0)$
      realen Kosten zu bezahlen.
    \item Zahle 1 \euro{} auf das Baumkonto f\"ur jeden neuen Baum
      beim L\"oschen des Minimums; 
      $O(\log n)$ \euro{} total.
    \item \"Uberweise 1 \euro{} vom Baumkonto auf das Knotenkonto
      f\"ur jeden neuen Knoten, der durch ein \texttt{link} 
      entsteht. Da jedes \texttt{link} die
      Anzahl der B\"aume verringert, reicht das Geld aus.
    \item Zahle 2 \euro{} auf das Baumkonto pro Baum
      nach dem Konsolidieren; $O(\log n)$ \euro{} total (wegen 
      Lemma~\ref{lem:additional_height}).
    \item Hebe $D$ \euro{} vom Knotenkonto ab, um  die
      $O(D)$ realen Kosten zu bezahlen.
      Da $D$ Knoten gel\"oscht werden, bleibt genug Geld auf dem
      Knotenkonto.
    \item Bei einem Erdbeben, \"uberweise  bis zu $2\texttt{n}[i]$
        \euro{} vom Einzelkinderkonto auf das Baumkonto, um 
	die evtl.~neu entstandenen B\"aume abzudecken.
	Hierbei ist $i$ die Ebene, auf der sich das Erdbeben
	ereignet.
  \end{enumerate}
  Die Buchhaltung deckt fast alle Kosten \"uber die Konten.
  Es verbleiben $O(\log n)$ \euro{} zu entrichten. Wir
  m\"ussen aber noch \"uberpr\"ufen, dass die Konteninvariante erhalten
  bleibt. F\"ur das Baumkonto und das Knotenkonto
  ist dies leicht zu sehen. F\"ur das Einzelkinderkonto brauchen
  wir das folgende Lemma. Es besagt, dass bei einem Erdbeben mindestens
  $\texttt{n}[i]/2$ innere Knoten mit nur einem Kind gel\"oscht werden
  \begin{lemma}\label{lem:onlychild}
    Sei $\texttt{n}[i+1] > \frac{3}{4}\texttt{n}[i]$. Dann
    enth\"alt Ebene $i+1$ mindestens $\texttt{n}[i]/2$ Knoten mit 
    nur einem Kind.
  \end{lemma}
  \begin{proof}[Beweis]
    Sei $n_1$ die Anzahl der Knoten auf Ebene $i+1$ mit einem Kind,
    $n_2$ die Anzahl der Knoten auf Ebene $i+1$ mit zwei Kindern und
    $n_0$ die Anzahl der Wurzeln auf Ebene $i$.
    Es gilt $\texttt{n}[i+1] = n_1 + n_2$ und
    $\texttt{n}[i] = n_0 + n_1 + 2n_2$.
    Laut Annahme ist
    \[
       n_1 + n_2 = \texttt{n}[i+1] > \frac{3}{4}\texttt{n}[i] 
       = \frac{3}{4}n_0 + \frac{3}{4}n_1 
          + \frac{3}{2}n_2.
    \]
    Daraus folgt $n_1 > 3n_0 + 2n_2 \geq n_0 + 2n_2$, und es gilt
    \[
      n_1 = \frac{n_1 + n_1}{2} > \frac{n_1 + n_0 + 2n_2}{2} = 
         \frac{\texttt{n}[i]}{2},
    \]
    was zu zeigen war.
  \end{proof}
  Aus Lemma~\ref{lem:onlychild} folgt, dass bei einem Erdbeben mindestens
  $4 \cdot \texttt{n}[i]/2 = 2\texttt{n}[i]$ \euro{} im 
  Einzelkinderkonto frei 
  werden, so dass die \"Uberweisung im letzten Schritt die Konteninvariante
  erh\"alt (\texttt{delete-min} erzeugt keine neuen 
  Einzelkinder).
  Damit ist die Analyse beendet.
\end{document}