# Why is removing the second largest element from a max-heap not in O(log n)?

I have a max PriorityQueue designed using a heap. A function removemax() that removes and returns the element with the largest priority in $\Theta(\log n)$ and a function insert in $\Theta(\log n)$ for the worst cases (both of them work with the heap by reorganizing it whenever necessary in order to retain the heap properties).

I am designing a function to remove the second largest element in the queue.

This is my algorithm assuing queue is a priority queue with the functions insert and removemax:

removesecondlargest(queue)
largest = queue.removemax()
secondlargest = queue.removemax()
queue.insert(largest)
return secondlargest


However, I am not sure why this approach isn't in $O(\log n)$ for the worst case?

Can someone explain me why?

• Huh, who says so? – Raphael Jan 20 '15 at 18:26
• It is $O(3 \log n)$, which is the same as $O(\log n)$. – jmite Jan 20 '15 at 18:30
• I noticed I was misreading the feedback I got. It seems to hold. – JOX Jan 20 '15 at 18:35