\section{Priority Queue}

\toclesssubsection{Introduction}

\begin{frame}{Priority Queue}{Introduction}
  \textbf{Definition:}
  \begin{itemize}
    \item<2->
      A priority queue saves a set of elements
    \item<3->
      Each element contains a key and a value like a map
    \item<4->
      There is a total order (like ${\color{Mittel-Blau}\leq}$) defined on the
      keys
  \end{itemize}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Introduction}
  \textbf{Definition:}
  \begin{itemize}
    \item<2->
      The priority queue supports the following operations:
  \end{itemize}
  \onslide<3->
  \begin{tabular}{ll}
    {\color{Mittel-Blau}\texttt{insert(key, value):}} &
    inserts a new element into the queue
  \end{tabular}
  \onslide<4->
  \begin{tabular}{ll}
    {\color{Mittel-Blau}\texttt{getMin():}} &
    returns the element with the smallest key\\
    {\color{Mittel-Blau}\texttt{deleteMin():}} &
    removes the element with the smallest key
  \end{tabular}
  \vspace{1.0em}
  \begin{itemize}
    \item<5->
      Sometimes additional operations are defined:
  \end{itemize}
  \onslide<6->
  \begin{tabular}{ll}
    {\color{Mittel-Blau}\texttt{changeKey(item, key):}} &
    changes the key of the element
  \end{tabular}
  \onslide<7->
  \begin{tabular}{ll}
    {\color{Mittel-Blau}\texttt{remove(item):}} &
    removes the element from the queue
  \end{tabular}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Introduction}
  \textbf{Special features:}
  \begin{itemize}
    \item<2->
      Multiple elements with the same key
      \begin{itemize}
        \item<3->
          No problem and for many applications necessary
        \item<3->
          If there is more than one element with the smallest key
          \begin{tabular}{ll}
            {\color{Mittel-Blau}\texttt{getMin():}} &
            returns just one of the possible elements\\
            {\color{Mittel-Blau}\texttt{deleteMin():}} &
            deletes the element returned by
            {\color{Mittel-Blau}\texttt{getMin}}
          \end{tabular}
      \end{itemize}
      \vspace{0.5em}
    \item<4->
      Argument of {\color{Mittel-Blau}\texttt{changeKey}} and
          {\color{Mittel-Blau}\texttt{remove}} operations
      \begin{itemize}
        \item<5->
          There is no \textbf{quick access} to an element in the queue
        \item<5->
          That is why {\color{Mittel-Blau}\texttt{insert}} and
          {\color{Mittel-Blau}\texttt{getMin}} return a reference
          (handle, accessor object)
        \item<5->
          {\color{Mittel-Blau}\texttt{changeKey}} and
          {\color{Mittel-Blau}\texttt{remove}} take this reference as argument
        \item<5->
          Therefore each element has to store its current position in the heap.
      \end{itemize}
  \end{itemize}
\end{frame}

%-------------------------------------------------------------------------------

\codeslide{python}{
\begin{frame}{Priority Queue}{Python}
  \vspace{-1.0em}
  \lstinputlisting[
    language=Python,
    basicstyle=\scriptesize,
    tabsize=4,
    style={python-idle-code},
    escapechar={@}
  ]{Code/PriorityQueue.py}
\end{frame}
}

%-------------------------------------------------------------------------------

\codeslide{java}{
\begin{frame}{Priority Queue}{Java}
  \lstinputlisting[
    language=Java,
    basicstyle=\scriptesize,
    tabsize=4,
    style={java-eclipse-code},
    breaklines=false,
    escapechar={@},
    emph={q,i1,i2},
    emphstyle=\color{java_variable}
  ]{Code/PriorityQueuePart1.java}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Java}
  \lstinputlisting[
    language=Java,
    basicstyle=\scriptesize,
    tabsize=4,
    style={java-eclipse-code},
    breaklines=false,
    escapechar={@},
    emph={q,i2,i3,i4},
    emphstyle=\color{java_variable}
  ]{Code/PriorityQueuePart2.java}
\end{frame}
}

%-------------------------------------------------------------------------------

\codeslide{cpp}{
\begin{frame}{Priority Queue}{C++}
  \lstinputlisting[
    language=C++,
    basicstyle=\small,
    tabsize=4,
    style={cpp-eclipse-code},
    breaklines=false,
    morekeywords={endl},
    escapechar={@}
  ]{Code/PriorityQueuePart1.cpp}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{C++}
  \vspace{-1.0em}
  \lstinputlisting[
    language=C++,
    basicstyle=\small,
    tabsize=4,
    style={cpp-eclipse-code},
    breaklines=false,
    morekeywords={endl},
    escapechar={@}
  ]{Code/PriorityQueuePart2.cpp}
\end{frame}
}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Application Example}
  \textbf{Example 1:}
  \begin{itemize}
    \item
      Calculation of the sorted union of $k$ sorted lists\\
      (multi-way merge or $k$-way merge)
  \end{itemize}
  \begin{figure}[!h]
    \begin{columns}
      \begin{column}[t]{0.5\linewidth}
        \begin{tabularx}{\linewidth}{c|X|X|X|X|X|}
          \cline{2-6}
          $L_1:$ & 3 & 5 & 8 & 12 & $\dots$\\
          \cline{2-6}
        \end{tabularx}
        \hfill\\[1.25em]
        \begin{tabularx}{\linewidth}{c|X|X|X|X|X|}
          \cline{2-6}
          $L_2:$ & 4 & 5 & 6 & 7 & $\dots$\\
          \cline{2-6}
        \end{tabularx}
      \end{column}
      \begin{column}[t]{0.5\linewidth}
        \begin{tabularx}{\linewidth}{c|X|X|X|X|X|}
          \cline{2-6}
          $L_3:$ & 1 & 10 & 11 & 24 & $\dots$\\
          \cline{2-6}
        \end{tabularx}
      \end{column}
    \end{columns}
    \hfill\\
    \onslide<2->
    $\underbrace{\hspace{\linewidth}}$\\[0.5em]
    \begin{tabularx}{\linewidth}{c|X|X|X|X|X|X|X|X|X|X|}
      \cline{2-11}
      $\Rightarrow R:$ & 1 & 3 & 4 & 5 & 5 & 6 & 7 & 8 & 10 & $\dots$\\
      \cline{2-11}
    \end{tabularx}
    \caption{3-way merge}
    \label{fig:priority_queue:three_way_merge}
  \end{figure}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Application Example}
  \textbf{Example 1:}
  \begin{itemize}
    \item<2->
      Calculation of the sorted union of ${\color{Mittel-Blau}k}$ sorted lists\\
      (multi-way merge or ${\color{Mittel-Blau}k}$-way merge)
    \item<3->
      Runtime:
      ${\color{Mittel-Blau}N}$ = length of resulting list
      \begin{itemize}
        \item<4->
          Trivial:
          \begin{math}
            \Theta({\color{Mittel-Blau}N} \cdot {\color{Mittel-Blau}k})
          \end{math},
          minimum calculation $\Theta({\color{Mittel-Blau}k})$
        \item<5->
          Priority queue:
          \begin{math}
            \Theta({\color{Mittel-Blau}N} \cdot \log {\color{Mittel-Blau}k})
          \end{math},
          minimum calculation  $\Theta(\log {\color{Mittel-Blau}k})$
      \end{itemize}
  \end{itemize}
  \onslide<6->
  \textbf{Example 2:}
  \begin{itemize}
    \item<7->
      For example Dijkstra's algorithm for computing the shortest path (following lecture)
    \item<8->
      Among other applications it can be used for sorting
  \end{itemize}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Implementation}
  \textbf{Idea:}
  \begin{itemize}
    \item<2->
      Save elements as tuples in a binary heap
    \item<3->
      Summary from lecture 1 (\textit{HeapSort}):
    \begin{itemize}
      \item<3->
        Nearly complete binary tree
      \item<3->
        {\color{Mittel-Blau}Heap condition}:\\
        The key of each node ${\color{Mittel-Blau}\leq}$ the keys of the
        children\\
    \end{itemize}
  \end{itemize}
  \vspace{-0.5em}
  \onslide<2->
  \begin{figure}[!h]
    \begin{adjustbox}{height=0.3\linewidth}
      \input{Images/GenericHeap.tikz}%
    \end{adjustbox}
    \vspace{-0.75em}
    \caption{heap with 11 nodes}%
    \label{fig:priority_queue:impl_heap}%
  \end{figure}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Implementation}
 \onslide<1->
 \begin{figure}[!h]%
   \vspace{-1.5em}
   \begin{minipage}[b]{0.4\linewidth}%
     \input{Images/PriorityQueue/Heap.tikz}%
    \end{minipage}
    \hfill
    \begin{tabular}[b]{ccccc}
      {\color{Mittel-Gruen}0}&
      {\color{Mittel-Gruen}1}&
      {\color{Mittel-Gruen}2}&
      {\color{Mittel-Gruen}3}&
      {\color{Mittel-Gruen}4}\\
      \hline
      \multicolumn{1}{|c}{4, {\color{green2}B}}&%
      \multicolumn{1}{|c}{8, {\color{green2}M}}&%
      \multicolumn{1}{|c}{5, {\color{green2}A}}&%
      \multicolumn{1}{|c}{17, {\color{green2}Q}}&%
      \multicolumn{1}{|c|}{9, {\color{green2}H}}\\
      \hline
    \end{tabular}
    \vspace{-0.5em}
    \caption{min heap stored in array}%
    \label{fig:priority_queue:impl_min_heap}%
  \end{figure}%
 \vspace{-1.0em}
 \onslide<2->
  \textbf{Storing a binary heap:}
  \begin{itemize}
    \item<3->
      Number nodes from top to bottom and left to right starting with 0
      and store entries in array
    \item<3->
      Children of node ${\color{Mittel-Blau}i}$ are the nodes
      ${\color{Mittel-Blau}2\,i+1}$ and ${\color{Mittel-Blau}2\,i+2}$
    \item<3->
      Parent node of node ${\color{Mittel-Blau}i}$ is
      $\displaystyle {\color{Mittel-Blau}\mathrm{floor}((i-1)/2)}$
  \end{itemize}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Implementation - Insertion}
  \textbf{Inserting an element:}
         {\color{Mittel-Blau}\texttt{insert(key, item)}}
           \begin{figure}[!h]
    \begin{adjustbox}{height=0.275\linewidth}
      \input{Images/PriorityQueue/Heap.tikz}%
    \end{adjustbox}
    \raisebox{3.0em}{
      \begin{math}
        \stackrel{
          \color{Mittel-Blau}\texttt{insert(1, {\color{green2}X})}
        }{\Rightarrow}
      \end{math}
    }\hspace{-1.5em}
    \begin{adjustbox}{height=0.275\linewidth}
      \input{Images/PriorityQueue/Heap_Insert.tikz}%
    \end{adjustbox}
    %    \vspace{-0.5em}
    %    \caption{Inserting into the priority queue}%
    \label{fig:priority_queue:impl_insert}%
  \end{figure}%
  \begin{itemize}
    \item<2->
      Append the element at the end of the array
    \item<3->
      The {\color{Mittel-Blau}heap condition} may be violated, but only at the
      last index
    \item<4->
      Repair {\color{Mittel-Blau}heap condition}
      $\Rightarrow$ We will see later how to do this
  \end{itemize}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Implementation}
  \textbf{Returning the minimum:}
         {\color{Mittel-Blau}\texttt{getMin()}}
          \begin{figure}[!h]
    \begin{adjustbox}{height=0.275\linewidth}
      \input{Images/PriorityQueue/Heap_Peek.tikz}%
    \end{adjustbox}
    \hspace{1.75em}\raisebox{3.0em}{
      $\stackrel{\color{Mittel-Blau}\texttt{getMin}}{\Rightarrow}$
      \hspace{1.75em}
      (4, {\color{green2}B})
    }
    \hfill
    %    \vspace{-0.5em}
    %    \caption{Returning the smallest element of the priotity queue}%
    \label{fig:priority_queue:impl_peek}%
  \end{figure}%
  \begin{itemize}
    \item<2->
      Else return the first element
    \item<3->
      If the heap is empty return {\color{Mittel-Blau}None}
  \end{itemize}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Implementation}
  \textbf{Removing the minimum:}
         {\color{Mittel-Blau}\texttt{deleteMin()}}
           \begin{figure}[!h]
    \begin{adjustbox}{height=0.275\linewidth}
      \input{Images/PriorityQueue/Heap_PrePop.tikz}%
    \end{adjustbox}
    \hspace{0.5em}\raisebox{3.0em}{
      $\stackrel{\color{Mittel-Blau}\texttt{deleteMin}}{\Rightarrow}$
    }\hspace{-1.5em}
    \begin{adjustbox}{height=0.275\linewidth}
      \input{Images/PriorityQueue/Heap_PostPop.tikz}%
    \end{adjustbox}
    %    \vspace{-0.5em}
    %    \caption{Removing the smallest element of the priotity queue}%
    \label{fig:priority_queue:impl_pop}%
  \end{figure}%
   \begin{itemize}
    \item<2->
     Deleting the element with the lowest key
    \item<3->
      Swap the last element with the first element and shrink the heap by one
    \item<4->
      The {\color{Mittel-Blau}heap condition} may be violated, but only at the
      first index
    \item<5->
      Repair {\color{Mittel-Blau}heap condition}
  \end{itemize}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Implementation}
  \textbf{Changing the key (priority):}
  {\color{Mittel-Blau}\texttt{changeKey(item, key)}}
  \begin{itemize}
    \item
      The element (queue item) is given as argument
    \item
      Replace the key of the element
    \item
      The {\color{Mittel-Blau}heap condition} may be violated, but only at the
      element index and only in one direction (up / down)
    \item
      Repair {\color{Mittel-Blau}heap condition}
  \end{itemize}
    \begin{figure}[!h]
      \begin{adjustbox}{height=0.275\linewidth}
        \input{Images/PriorityQueue/Heap_PreChangeKey.tikz}%
      \end{adjustbox}
      \hspace{0.25em}\raisebox{3.0em}{
        $\stackrel{\color{Mittel-Blau}\texttt{changeKey}}{\Rightarrow}$
      }\hspace{-1.5em}
      \begin{adjustbox}{height=0.275\linewidth}
        \input{Images/PriorityQueue/Heap_PostChangeKey.tikz}%
      \end{adjustbox}
      %    \vspace{-0.5em}
      %    \caption{Changing the key of an element}%
      \label{fig:priority_queue:impl_change_key}%
    \end{figure}%
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Implementation}
  \textbf{Changing the key (priority):}
   {\color{Mittel-Blau}\texttt{changeKey(item, key)}}
     \begin{figure}[!h]
      \begin{adjustbox}{height=0.275\linewidth}
        \input{Images/PriorityQueue/Heap_PreChangeKey.tikz}%
      \end{adjustbox}
      \hspace{0.25em}\raisebox{3.0em}{
        $\stackrel{\color{Mittel-Blau}\texttt{changeKey}}{\Rightarrow}$
      }\hspace{-1.5em}
      \begin{adjustbox}{height=0.275\linewidth}
        \input{Images/PriorityQueue/Heap_PostChangeKey2.tikz}%
      \end{adjustbox}
      %    \vspace{-0.5em}
      %    \caption{Changing the key of an element}%
      \label{fig:priority_queue:impl_change_key2}%
    \end{figure}%
  \begin{itemize}
    \item<2->
      The {\color{Mittel-Blau}heap condition} may be violated, but only at the
      element index and only in one direction (up / down)
    \item<3->
      Repair {\color{Mittel-Blau}heap condition}
  \end{itemize}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Implementation}
  \textbf{Removing an element:}
   {\color{Mittel-Blau}\texttt{remove(item)}}
     \begin{figure}[!h]
      \begin{adjustbox}{height=0.275\linewidth}
        \input{Images/PriorityQueue/Heap_PreRemove.tikz}%
      \end{adjustbox}
      \hspace{0.5em}\raisebox{3.0em}{
        $\stackrel{\color{Mittel-Blau}\texttt{remove}}{\Rightarrow}$
      }\hspace{-1.0em}
      \begin{adjustbox}{height=0.275\linewidth}
        \input{Images/PriorityQueue/Heap_PostRemove.tikz}%
      \end{adjustbox}
      %    \vspace{-0.5em}
      %    \caption{Removing a random element from the priotity queue}%
      \label{fig:priority_queue:impl_remove}%
    \end{figure}%
  \begin{itemize}
    \item<2->
      The element (queue item) is given as argument
    \item<3->
      Replace the element with the last element and shrink the heap by one
    \item<4->
      The {\color{Mittel-Blau}heap condition} may be violated, but only at the
      element index and only in one direction (up / down)
    \item<5->
      Repair {\color{Mittel-Blau}heap condition}
  \end{itemize}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Implementation - Reparing the Heap}
  \textbf{Repairing after modifying operations:}
  \begin{itemize}
    \item<2->
      The heap condition can be violated after using
      {\color{Mittel-Blau}\texttt{insert}},
      {\color{Mittel-Blau}\texttt{deleteMin}},
      {\color{Mittel-Blau}\texttt{changeKey}},
      {\color{Mittel-Blau}\texttt{remove}},
      but only at one known position with index ${\color{Mittel-Blau}i}$
    \item<3->
      Heap conditions can be violated in two directions:
      \begin{itemize}
        \item<4->
          Downwards:
          the key at index ${\color{Mittel-Blau}i}$ is not
          ${\color{Mittel-Blau}\leq}$ than the value of its children
        \item<5->
          Upwards:
          the key at index ${\color{Mittel-Blau}i}$ is not
          ${\color{Mittel-Blau}\geq}$ than the value of its parent
      \end{itemize}
    \item<6->
      We need two repair methods:
      {\color{Mittel-Blau}\texttt{repairHeapUp}},
      {\color{Mittel-Blau}\texttt{repairHeapDown}}
  \end{itemize}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Implementation - Reparing the Heap}
  {\color{Mittel-Blau}\texttt{\textbf{repairHeapDown:}}}
  \begin{itemize}
    \item<2->
      {\color{Mittel-Blau}Sift} the element until the
      {\color{Mittel-Blau}heap condition} is valid
      \begin{itemize}
        \item<3->
          Change node with child, which has the lower key of both children
        \item<4->
          If the {\color{Mittel-Blau}heap condition} is violated repeat for
          the child node
      \end{itemize}
  \end{itemize}
   \begin{figure}[!h]%
    \begin{columns}%
      \begin{column}{0.45\linewidth}%
        \begin{adjustbox}{width=\linewidth}%
          \input{Images/PriorityQueue/HeapRepairDown_First.tikz}%
        \end{adjustbox}%
      \end{column}%
      \begin{column}{0.45\linewidth}%
        \begin{adjustbox}{width=\linewidth}%
          \input{Images/PriorityQueue/HeapRepairDown_Second.tikz}%
        \end{adjustbox}%
      \end{column}%
    \end{columns}%
    \caption{repairing the heap downwards}%
    \label{fig:priority_queue:impl_repair_heap_down}%
  \end{figure}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Implementation - Reparing the Heap}
  {\color{Mittel-Blau}\texttt{\textbf{repairHeapDown:}}}
  \begin{itemize}
    \item
      {\color{Mittel-Blau}Sift} the element until the
      {\color{Mittel-Blau}heap condition} is valid
      \begin{itemize}
        \item
          Change node with child, which has the lower key of both children
        \item
          If the {\color{Mittel-Blau}heap condition} is violated repeat for
          the child node
      \end{itemize}
  \end{itemize}
  \begin{center}
    \begin{figure}[!h]%
      \begin{columns}%
        \begin{column}{0.45\linewidth}%
          \begin{adjustbox}{width=\linewidth}%
              \input{Images/PriorityQueue/HeapRepairDown_Second.tikz}%
          \end{adjustbox}%
        \end{column}%
        \begin{column}{0.45\linewidth}%
          \begin{adjustbox}{width=\linewidth}%
            \input{Images/PriorityQueue/HeapRepairDown_Third.tikz}%
          \end{adjustbox}%
        \end{column}%
      \end{columns}%
      \caption{repairing the heap downwards}%
      \label{fig:priority_queue:impl_repair_heap_down2}%
    \end{figure}
  \end{center}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Implementation - Reparing the Heap}
  {\color{Mittel-Blau}\texttt{\textbf{repairHeapUp:}}}
  \begin{itemize}
    \item<2->
      Change node with parent
    \item<3->
      If the {\color{Mittel-Blau}heap condition} is violated repeat for parent
      node
  \end{itemize}
  \begin{center}
    \begin{figure}[!h]%
      \begin{columns}%
        \begin{column}{0.45\linewidth}%
          \begin{adjustbox}{width=\linewidth}%
            \input{Images/PriorityQueue/HeapRepairUp_First.tikz}%
          \end{adjustbox}%
        \end{column}%
        \begin{column}{0.45\linewidth}%
          \begin{adjustbox}{width=\linewidth}%
            \input{Images/PriorityQueue/HeapRepairUp_Second.tikz}%
          \end{adjustbox}%
        \end{column}%
      \end{columns}%
      \caption{repairing the heap upwards}%
      \label{fig:priority_queue:impl_repair_heap_up}%
    \end{figure}
  \end{center}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Implementation - Reparing the Heap}
  {\color{Mittel-Blau}\texttt{\textbf{repairHeapUp:}}}
  \begin{itemize}
    \item
      Change node with parent
    \item
      If the {\color{Mittel-Blau}heap condition} is violated repeat for parent
      node
  \end{itemize}
  \begin{center}
    \begin{figure}[!h]%
      \begin{columns}%
        \begin{column}{0.45\linewidth}%
          \begin{adjustbox}{width=\linewidth}%
            \input{Images/PriorityQueue/HeapRepairUp_Second.tikz}%
          \end{adjustbox}%
        \end{column}%
        \begin{column}{0.45\linewidth}%
          \begin{adjustbox}{width=\linewidth}%
            \input{Images/PriorityQueue/HeapRepairUp_Third.tikz}%
          \end{adjustbox}%
        \end{column}%
      \end{columns}%
      \caption{repairing the heap upwards}%
      \label{fig:priority_queue:impl_repair_heap_up2}%
    \end{figure}
  \end{center}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Implementation - Priority Queue Item}
  \textbf{Index of a priority queue item:}
  \begin{itemize}
    \item<2->
      {\color{red}Attention:}
      for {\color{Mittel-Blau}\texttt{changeKey}} and
      {\color{Mittel-Blau}\texttt{remove}} the item has to \enquote{know} where
      it is located in the heap
    \item<3->
      Remember for {\color{Mittel-Blau}\texttt{repairHeapUp}} and
      {\color{Mittel-Blau}\texttt{repairHeapDown}}:\\
      update the index if moving an heap element
  \end{itemize}
\end{frame}

%-------------------------------------------------------------------------------

\codeslide{python}{
\begin{frame}{Priority Queue}{Implementation - Priority Queue Item - Python}
  \lstinputlisting[
    language=Python,
    basicstyle=\scriptesize,
    tabsize=4,
    style={python-idle-code},
    escapechar={@},
    emph={PriorityQueueItem, __init__},
    emphstyle=\color{blue}
  ]{Code/PriorityQueueItem.py}
\end{frame}
}

%-------------------------------------------------------------------------------

\codeslide{java}{
\begin{frame}{Priority Queue}{Implementation - Priority Queue Item - Java}
  \lstinputlisting[
    language=Java,
    basicstyle=\scriptesize,
    tabsize=4,
    style={java-eclipse-code},
    breaklines=false,
    mathescape=true,
    emph={key, value, heapIndex},
    emphstyle=\color{java_static}
  ]{Code/PriorityQueueItem.java}
\end{frame}
}

%-------------------------------------------------------------------------------

\codeslide{cpp}{
\begin{frame}{Priority Queue}{Implementation - Priority Queue Item - C++}
  \lstinputlisting[
    language=C++,
    basicstyle=\small,
    tabsize=4,
    style={cpp-eclipse-code},
    breaklines=false,
    morekeywords={endl},
    escapechar={@}
  ]{Code/PriorityQueueItem.cpp}
\end{frame}
}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Complexity}
  \textbf{Summary lecture 1:}
  \begin{itemize}
    \item<2->
      A full binary tree with {\color{Mittel-Blau}$n$} elements has a {\color{Mittel-Blau}depth} of
      {\color{Mittel-Blau}$O(\log n)$}
    \item<3->
      The maximum distance from the root to a leaf can be
      $O(\log n)$ elements
    \item<4->
      Repairing the heap upwards and downwards:\\
      We have only one path to traverse: {\color{Mittel-Blau}$O(\log n)$}
  \end{itemize}
  \onslide<5->
  \textbf{Runtime for methods}
  \begin{itemize}
    \item<6->
      {\color{Mittel-Blau}\texttt{insert}},
      {\color{Mittel-Blau}\texttt{deleteMin}},
      {\color{Mittel-Blau}\texttt{changeKey}},
      {\color{Mittel-Blau}\texttt{remove}}:\\
      we have to repair the heap: {\color{Mittel-Blau}$O(\log n)$}
    \item<7->
      {\color{Mittel-Blau}\texttt{getMin}}:
      return the element at index 0: {\color{Mittel-Blau}$O(1)$}
  \end{itemize}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Priority Queue}{Complexity}
  \textbf{Improvements (Fibonacci heaps):}
  \begin{itemize}
    \item<2->
      {\color{Mittel-Blau}\texttt{getMin}},
      {\color{Mittel-Blau}\texttt{insert}} and
      {\color{Mittel-Blau}\texttt{decreaseKey}}
      in amortized time of {\color{Mittel-Blau}$O(1)$}
    \item<3->
      {\color{Mittel-Blau}\texttt{deleteMin}}
      in amortized time {\color{Mittel-Blau}$O(\log n)$}
  \end{itemize}
  \hfill\\[0.5em]
  \onslide<4->
  \textbf{Practical experience:}
  \begin{itemize}
    \item<5->
      The binary heap is simpler: costs for managing the structure are low
    \item<6->
      The difference is negligible if the number of elements is relatively small 
    \item<7->
      Example:
    \begin{itemize}
      \item
        For ${\color{Mittel-Blau}n = 2^{10}} \approx 1,000$, the
        {\color{Mittel-Blau}depth}
        $\log_2 n$ is only 10
      \item
        For ${\color{Mittel-Blau}n = 2^{20}} \approx 1,000,000$, the
        {\color{Mittel-Blau}depth}
        $\log_2 n$ is only 20
    \end{itemize}
  \end{itemize}
\end{frame}
