\hypertarget{a00693}{\section{A\+C\+G\+:\+:Heap\+T$<$ Heap\+Entry, Heap\+Interface $>$ Class Template Reference}
\label{a00693}\index{A\+C\+G\+::\+Heap\+T$<$ Heap\+Entry, Heap\+Interface $>$@{A\+C\+G\+::\+Heap\+T$<$ Heap\+Entry, Heap\+Interface $>$}}
}


{\ttfamily \#include $<$A\+C\+G/\+Utils/\+Heap\+T.\+hh$>$}

Inheritance diagram for A\+C\+G\+:\+:Heap\+T$<$ Heap\+Entry, Heap\+Interface $>$\+:\begin{figure}[H]
\begin{center}
\leavevmode
\includegraphics[height=2.000000cm]{a00693}
\end{center}
\end{figure}
\subsection*{Public Types}
\begin{DoxyCompactItemize}
\item 
\hypertarget{a00693_a277c1530acc11fd7d7920a4b5d9c27d3}{typedef std\+::vector$<$ Heap\+Entry $>$ {\bfseries Base}}\label{a00693_a277c1530acc11fd7d7920a4b5d9c27d3}

\end{DoxyCompactItemize}
\subsection*{Public Member Functions}
\begin{DoxyCompactItemize}
\item 
\hypertarget{a00693_a61294d7b3ac96f2f12504211123c1bfa}{\hyperlink{a00693_a61294d7b3ac96f2f12504211123c1bfa}{Heap\+T} ()}\label{a00693_a61294d7b3ac96f2f12504211123c1bfa}

\begin{DoxyCompactList}\small\item\em Constructor. \end{DoxyCompactList}\item 
\hypertarget{a00693_a0da742f2ad1b15573ba81828ecf64b15}{\hyperlink{a00693_a0da742f2ad1b15573ba81828ecf64b15}{Heap\+T} (const Heap\+Interface \&\+\_\+interface)}\label{a00693_a0da742f2ad1b15573ba81828ecf64b15}

\begin{DoxyCompactList}\small\item\em Construct with a given {\ttfamily Heap\+Iterface}. \end{DoxyCompactList}\item 
\hypertarget{a00693_adcfe4c6df9c9da2986414cdef839645b}{\hyperlink{a00693_adcfe4c6df9c9da2986414cdef839645b}{$\sim$\+Heap\+T} ()}\label{a00693_adcfe4c6df9c9da2986414cdef839645b}

\begin{DoxyCompactList}\small\item\em Destructor. \end{DoxyCompactList}\item 
\hypertarget{a00693_a98d3dea1f49362d1bd5cff8fd1664cbc}{void \hyperlink{a00693_a98d3dea1f49362d1bd5cff8fd1664cbc}{clear} ()}\label{a00693_a98d3dea1f49362d1bd5cff8fd1664cbc}

\begin{DoxyCompactList}\small\item\em clear the heap \end{DoxyCompactList}\item 
\hypertarget{a00693_ad709062d6808618dd40cb42d209a5987}{bool \hyperlink{a00693_ad709062d6808618dd40cb42d209a5987}{empty} ()}\label{a00693_ad709062d6808618dd40cb42d209a5987}

\begin{DoxyCompactList}\small\item\em is heap empty? \end{DoxyCompactList}\item 
\hypertarget{a00693_a8e293187d069ef6d10bb7778cedbb93d}{unsigned int \hyperlink{a00693_a8e293187d069ef6d10bb7778cedbb93d}{size} ()}\label{a00693_a8e293187d069ef6d10bb7778cedbb93d}

\begin{DoxyCompactList}\small\item\em returns the size of heap \end{DoxyCompactList}\item 
\hypertarget{a00693_ae4a14733513b75c349af8283a4ac3fbd}{void \hyperlink{a00693_ae4a14733513b75c349af8283a4ac3fbd}{reserve} (unsigned int \+\_\+n)}\label{a00693_ae4a14733513b75c349af8283a4ac3fbd}

\begin{DoxyCompactList}\small\item\em reserve space for \+\_\+n entries \end{DoxyCompactList}\item 
\hypertarget{a00693_a76cca23465f406eeca9ce36566cd6c67}{void \hyperlink{a00693_a76cca23465f406eeca9ce36566cd6c67}{reset\+\_\+heap\+\_\+position} (Heap\+Entry \+\_\+h)}\label{a00693_a76cca23465f406eeca9ce36566cd6c67}

\begin{DoxyCompactList}\small\item\em reset heap position to -\/1 (not in heap) \end{DoxyCompactList}\item 
\hypertarget{a00693_a3c6b5bf6193c0a6a30e585356b306ed2}{bool \hyperlink{a00693_a3c6b5bf6193c0a6a30e585356b306ed2}{is\+\_\+stored} (Heap\+Entry \+\_\+h)}\label{a00693_a3c6b5bf6193c0a6a30e585356b306ed2}

\begin{DoxyCompactList}\small\item\em is an entry in the heap? \end{DoxyCompactList}\item 
\hypertarget{a00693_ab37fa6947306fd8431f8c92a7f7ca884}{void \hyperlink{a00693_ab37fa6947306fd8431f8c92a7f7ca884}{insert} (Heap\+Entry \+\_\+h)}\label{a00693_ab37fa6947306fd8431f8c92a7f7ca884}

\begin{DoxyCompactList}\small\item\em insert the entry \+\_\+h \end{DoxyCompactList}\item 
\hypertarget{a00693_ae06d55fb2812a55c6c2f5076ca3dd789}{Heap\+Entry \hyperlink{a00693_ae06d55fb2812a55c6c2f5076ca3dd789}{front} ()}\label{a00693_ae06d55fb2812a55c6c2f5076ca3dd789}

\begin{DoxyCompactList}\small\item\em get the first entry \end{DoxyCompactList}\item 
\hypertarget{a00693_a5e30153db88e02f89b0e47949479792a}{void \hyperlink{a00693_a5e30153db88e02f89b0e47949479792a}{pop\+\_\+front} ()}\label{a00693_a5e30153db88e02f89b0e47949479792a}

\begin{DoxyCompactList}\small\item\em delete the first entry \end{DoxyCompactList}\item 
\hypertarget{a00693_ac6cbbfe2bbe8ad25ae29318a2f76b2b6}{void \hyperlink{a00693_ac6cbbfe2bbe8ad25ae29318a2f76b2b6}{remove} (Heap\+Entry \+\_\+h)}\label{a00693_ac6cbbfe2bbe8ad25ae29318a2f76b2b6}

\begin{DoxyCompactList}\small\item\em remove an entry \end{DoxyCompactList}\item 
void \hyperlink{a00693_a7d1277508ebf0bf26eab77f8b1aff2c4}{update} (Heap\+Entry \+\_\+h)
\item 
\hypertarget{a00693_ab109caa6f8b6da5acf87d8ffa6588790}{bool \hyperlink{a00693_ab109caa6f8b6da5acf87d8ffa6588790}{check} ()}\label{a00693_ab109caa6f8b6da5acf87d8ffa6588790}

\begin{DoxyCompactList}\small\item\em check heap condition \end{DoxyCompactList}\end{DoxyCompactItemize}
\subsection*{Private Types}
\begin{DoxyCompactItemize}
\item 
\hypertarget{a00693_a361037a521f50fd3ff72980e2dfd8efe}{typedef std\+::vector$<$ Heap\+Entry $>$ {\bfseries Heap\+Vector}}\label{a00693_a361037a521f50fd3ff72980e2dfd8efe}

\end{DoxyCompactItemize}
\subsection*{Private Member Functions}
\begin{DoxyCompactItemize}
\item 
\hypertarget{a00693_a94f468a9fe4deceaf2086fa478710df4}{void \hyperlink{a00693_a94f468a9fe4deceaf2086fa478710df4}{upheap} (unsigned int \+\_\+idx)}\label{a00693_a94f468a9fe4deceaf2086fa478710df4}

\begin{DoxyCompactList}\small\item\em Upheap. Establish heap property. \end{DoxyCompactList}\item 
\hypertarget{a00693_abe9af5d9fc16146e74f7ca4e0199c4f3}{void \hyperlink{a00693_abe9af5d9fc16146e74f7ca4e0199c4f3}{downheap} (unsigned int \+\_\+idx)}\label{a00693_abe9af5d9fc16146e74f7ca4e0199c4f3}

\begin{DoxyCompactList}\small\item\em Downheap. Establish heap property. \end{DoxyCompactList}\item 
\hypertarget{a00693_a33306ce9f5746d5439430e6a5f222477}{Heap\+Entry \hyperlink{a00693_a33306ce9f5746d5439430e6a5f222477}{entry} (unsigned int \+\_\+idx)}\label{a00693_a33306ce9f5746d5439430e6a5f222477}

\begin{DoxyCompactList}\small\item\em Get the entry at index \+\_\+idx. \end{DoxyCompactList}\item 
\hypertarget{a00693_acb01f8df0178d41a2b668c3774bb547a}{void \hyperlink{a00693_acb01f8df0178d41a2b668c3774bb547a}{entry} (unsigned int \+\_\+idx, Heap\+Entry \+\_\+h)}\label{a00693_acb01f8df0178d41a2b668c3774bb547a}

\begin{DoxyCompactList}\small\item\em Set entry \+\_\+h to index \+\_\+idx and update \+\_\+h's heap position. \end{DoxyCompactList}\item 
\hypertarget{a00693_a1d29f453970327a5e2fdd4dfc25e48f5}{unsigned int \hyperlink{a00693_a1d29f453970327a5e2fdd4dfc25e48f5}{parent} (unsigned int \+\_\+i)}\label{a00693_a1d29f453970327a5e2fdd4dfc25e48f5}

\begin{DoxyCompactList}\small\item\em Get parent's index. \end{DoxyCompactList}\item 
\hypertarget{a00693_a8d5d053eef5fd2825aad7402b0fd5348}{unsigned int \hyperlink{a00693_a8d5d053eef5fd2825aad7402b0fd5348}{left} (unsigned int \+\_\+i)}\label{a00693_a8d5d053eef5fd2825aad7402b0fd5348}

\begin{DoxyCompactList}\small\item\em Get left child's index. \end{DoxyCompactList}\item 
\hypertarget{a00693_a863b11b618cdb9fdb53b086d6aa7dc39}{unsigned int \hyperlink{a00693_a863b11b618cdb9fdb53b086d6aa7dc39}{right} (unsigned int \+\_\+i)}\label{a00693_a863b11b618cdb9fdb53b086d6aa7dc39}

\begin{DoxyCompactList}\small\item\em Get right child's index. \end{DoxyCompactList}\end{DoxyCompactItemize}
\subsection*{Private Attributes}
\begin{DoxyCompactItemize}
\item 
\hypertarget{a00693_af3740bc63532eb37d6940c5e00f217ad}{Heap\+Interface \hyperlink{a00693_af3740bc63532eb37d6940c5e00f217ad}{interface\+\_\+}}\label{a00693_af3740bc63532eb37d6940c5e00f217ad}

\begin{DoxyCompactList}\small\item\em Instance of Heap\+Interface. \end{DoxyCompactList}\end{DoxyCompactItemize}


\subsection{Detailed Description}
\subsubsection*{template$<$class Heap\+Entry, class Heap\+Interface = Heap\+Entry$>$class A\+C\+G\+::\+Heap\+T$<$ Heap\+Entry, Heap\+Interface $>$}

An efficient, highly customizable heap.

The main difference (and performace boost) of this heap compared to e.\+g. the heap of the S\+T\+L is that here to positions of the heap's elements are accessible from the elements themself. Therefore if one changes the priority of an element one does not have to remove and re-\/insert this element, but can just call the \hyperlink{a00693_a7d1277508ebf0bf26eab77f8b1aff2c4}{update(\+Heap\+Entry)} method.

This heap class is parameterized by two template arguments\+: \begin{DoxyItemize}
\item the class {\ttfamily Heap\+Entry}, that will be stored in the heap \item the Heap\+Interface telling the heap how to compare heap entries and how to store the heap positions in the heap entries. \end{DoxyItemize}


Definition at line 121 of file Heap\+T.\+hh.



\subsection{Member Function Documentation}
\hypertarget{a00693_a7d1277508ebf0bf26eab77f8b1aff2c4}{\index{A\+C\+G\+::\+Heap\+T@{A\+C\+G\+::\+Heap\+T}!update@{update}}
\index{update@{update}!A\+C\+G\+::\+Heap\+T@{A\+C\+G\+::\+Heap\+T}}
\subsubsection[{update}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class Heap\+Entry , class Heap\+Interface  = Heap\+Entry$>$ void {\bf A\+C\+G\+::\+Heap\+T}$<$ Heap\+Entry, Heap\+Interface $>$\+::update (
\begin{DoxyParamCaption}
\item[{Heap\+Entry}]{\+\_\+h}
\end{DoxyParamCaption}
)\hspace{0.3cm}{\ttfamily [inline]}}}\label{a00693_a7d1277508ebf0bf26eab77f8b1aff2c4}
update an entry\+: change the key and update the position to reestablish the heap property. 

Definition at line 204 of file Heap\+T.\+hh.



The documentation for this class was generated from the following file\+:\begin{DoxyCompactItemize}
\item 
A\+C\+G/\+Utils/Heap\+T.\+hh\end{DoxyCompactItemize}
