HeapReplace & hmqUpdate

    \subsubsection{Analyse de la complexité temporelle}

     En analysant le pseudocode de \textsc{HeapReplace}, on se rend compte que la seule opération coûteuse est l'appel de la procédure \textsc{heapify} aux lignes 5 \& 6. Sachant que cette procédure est appelée i fois avec $i = \floor{\text{heap.size}} / 2$,  on conclut donc que la complexité de \textsc{HeapReplace} est égal à celle de \textsc{heapify} à une constante multiplication près. Analysons donc la complexité de \textsc{heapify}.
    \begin{itemize}
        \item Dans le meilleur des cas, la variable \textsc{largest} est toujours différente de i lors de chaque appel de \textsc{heapify}. Dès lors, la complexité de \textsc{heapify} vaut $T(n) = \Theta(log (n))$ qui correspond à la hauteur du noeud d'où découle la complexité de \textsc{HeapReplace} : $T(n) = \frac{n}{2} * log(n)$

        \item Dans le pire des cas, la variable \textsc{largest} est égal à i à chaque itération ce qui revient à créer les tas en insérant les éléments tour à tour. Calculons le nombre N d'opération à effectuer dans un tel cas.
        On a $N =\sum_{i = 0}^{\log(n)} \frac{n*i}{2^{i+1}} = \frac{n}{2} * (\sum_{i = 0}^{\log(n)} i(\frac{1}{2})^{i})$. Nous allons maintenant résoudre cette dernière égalité en approchant le résultat. Sachant que $\frac{n}{2} * (\sum_{i = 0}^{\log(n)} i(\frac{1}{2})^{i}) \leq \frac{n}{2} * (\sum_{i = 0}^{\infty} i(\frac{1}{2})^{i})$ et que $\sum_{i = 1}^{\infty} i * x^{i} = \frac{x}{(1-x)^{2}}$. On arrive finalement sur le résultat suivant : $N \leq \frac{n}{2} * 2 = n$.
        En conclusion, la complexité de \textsc{heapify} vaut $\Theta (n)$ d'où découle la complexité de \textsc{HeapReplace} : $T(n) = \frac{n}{2} * n + C = \Theta(\frac{n^{2}}{2})$
    \end{itemize}

    \subsection{\textsc{mqUpdate} dans le cas des tas}

     On va chercher à décrire la complexité de \textsc{hmqUpdate} en fonction de la taille de la fenêtre $w$. On remarque que la seule opération coûteuse est l'appel de la procédure \textsc{heapReplace}. Déduction de la complexité en fonction des résultats précédents ?
    \begin{itemize}
        \item Dans le pire des cas, \textsc{hmqUpdate}
        \item Dans le meilleur des cas,
    \end{itemize}