Binary heap removal peculiar potential function analysis Given the potential function $\phi$, it seems that remove max may take $O(1)$ amoratized,
meaning that $n$ removals would take $O(n)$, which can't be, as it means we get a linear time comparison based sort if we build the heap in $O(n)$.

Where is the falling point in this potential function, and does it not give a $O(1)$ time guarantee and why?

\begin{align*}
    \overline C_i     =&amp;  C_i + \phi_i-\phi_{i-1} \\
    \phi_i  =&amp; \sum_{a\in Heap}{depth(a)} \\
\end{align*}


meaning the potential function is the sum of depths of all nodes in the tree.
\begin{align*}
    C_i           &amp;= \log n \\
    \phi_{i}      &amp;= \phi_{i-1} - \log n \\
    \overline C_i &amp;= \log n + \phi_{i-1} - \log n - \phi_{i-1} = 0
\end{align*}
Amortized analysis relies on $\sum_{i=1}^n \overline{C_i} = \sum_{i=1}^n C_i+\phi_n-\phi_0$ being an upper bound for $\sum_{i=1}^n C_i$. This requires $\phi_n$ to be at least as large as $\phi_0$. Your potential function does not satisfy this requirement, aince $\phi$ will get smaller with each step.