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:

    largest = queue.removemax()
    secondlargest = queue.removemax()
    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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.