\documentclass{paper}

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

\usepackage{fullpage}
\usepackage {amssymb}
\usepackage {amsmath}
\usepackage {amsthm}
%\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}
\newcommand{\DKL}{D_\textup{KL}}

\newtheorem{theorem}{Theorem}[section]
\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{Bin\"are Heaps}
\author{Wolfgang Mulzer}

\begin{document}
\maketitle

\section{Datenstruktur}

Ein bin\"arer Heap ist ein vollst\"angdiger bin\"arer
Baum mit der \emph{Heap-Eigenschaft}. Jeder Knoten hat
bis zu $2$ Kinder. Alle Ebenen bis auf die letzte 
sind voll besetzt. Die letzte Ebene ist von links
besetzt. Die Elemente stehen in den Knoten.
Das Element in einem Elternknoten ist kleiner oder gleich
den Elementen in den Kindknoten (Min-Heap Eigenschaft).
Bin\"are Heaps werden oft als Arrays gespeichert.
Sei \texttt{elements} das entsprechende Array.
Die Wurzel des Heaps steht bei Index 0.
Die Indizes der Kind- und der Elternknoten werden 
folgenderma\ss{}en berechnet.
\begin{verbatim}
  left(i) = 2i + 1
  right(i) = 2i + 2
  parent(i) = floor((i+1)/2) - 1
\end{verbatim}

\section{Implementierung der Operationen}

\texttt{size()} und \texttt{isEmpty()} werden mit Hilfe
eine eigenen Z\"ahlers \texttt{size} implementiert.
F\"ur \texttt{findMin()} muss man nur
\texttt{elements[0]} inspizieren.
F\"ur \texttt{deleteMin()} ersetzen wir
die Wurzel durch \texttt{elements[size-1]}
und dekrementieren \texttt{size}.
Dann f\"uhren wir \texttt{bubble-down(0)} aus.
F\"ur \texttt{insert(x)} schreiben wir \texttt{x} an
die Stelle \texttt{elements[size]}, inkrementieren
\texttt{size} und f\"uhren 
\texttt{bubble-up(size-1)} aus. 


\section{Absenken}\label{sec:bubble-down}

\begin{verbatim}
bubble-down(i)
  while( (left(i) < size && elements[left(i)] < elements[i]) ||
         (right(i) < size && elements[right(i)] < elements[i]) ) 
    nextI <- left(i)
    if right(i) < size && elements[right(i)] < elements[left(i)] then 
      nextI++
    elements[i] <-> elements[nextI]
    i <- nextI
\end{verbatim}


\section{Anheben}\label{sec:bubble-up}

\begin{verbatim}
bubble-up(i)
  while (i > 0 && elements[parent(i)] > elements[i])
    elements[parent(i)] <-> elements[i]
    i <- parent(i)
\end{verbatim}

\end{document}