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 =& C_i + \phi_i-\phi_{i-1} \\ \phi_i =& \sum_{a\in Heap}{height(a)} \\ \end{align*}

• meaning the potential function is the sum of heights of all nodes in the tree. \begin{align*} C_i &= \log n \\ \phi_{i} &= \phi_{i-1} - \log n \\ \overline C_i &= \log n + \phi_{i-1} - \log n - \phi_{i-1} = 0 \end{align*}

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 =& C_i + \phi_i-\phi_{i-1} \\ \phi_i =& \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 &= \log n \\ \phi_{i} &= \phi_{i-1} - \log n \\ \overline C_i &= \log n + \phi_{i-1} - \log n - \phi_{i-1} = 0 \end{align*}

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 it the falling point in this potential function, and does it not give a $O(1)$ time guarantee and why?

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

• meaning the potential function is the sum of heights of all nodes in the tree. \begin{align*} C_i &= \log n \\ \phi_{i} &= \phi_{i-1} - \log n \\ \overline C_i &= \log n + \phi_{i-1} - \log n - \phi_{i-1} = 0 \end{align*}

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 =& C_i + \phi_i-\phi_{i-1} \\ \phi_i =& \sum_{a\in Heap}{height(a)} \\ \end{align*}

• meaning the potential function is the sum of heights of all nodes in the tree. \begin{align*} C_i &= \log n \\ \phi_{i} &= \phi_{i-1} - \log n \\ \overline C_i &= \log n + \phi_{i-1} - \log n - \phi_{i-1} = 0 \end{align*}