If the queue has currently n elements, while (!q.empty() && q.back() > new_element) q.pop_back();
this part will take O(n) time if i am right?
#Why's this O(1)?
topaz mural
smoky mothBOT
cosmic light
its not
well
its not worst case O(1) which is what youre thinking
Depending on the input values it could be average case O(1)
(if the while loop basically never executes)
This push operation seems a bit weird though anyway, why would you need to pop things first
ah wait theyre using the queue has a min heap?
anyway tl;dr this is strange, and theyre wrong
summer wasp
If the queue has currently n elements, `while (!q.empty() && q.back() > new_elem...
It is clear
No the fuck it's not 🐒
But yeah, I think they're right because an .add in their case just discards whatever elements were greater and never actually bothers about re-inserting them. So, in the worst case, a single .add can lead to the entire queue being cleared, except for the element we just inserted. If they were re-inserting the elements, then it would be O(n) average case.
The same logic applies to removing an element, as a single remove can again cause the entire queue being cleared. If they were iterating over the list and only removed the element they needed to, then it would be O(n) average case again.
But yeah, in this case each element can get inserted, and then on the next access, be that for a lookup of any reason, we instantly remove it. This means that for each element we have a total of 2 accesses: The first access creates the element and the next access, regardless of what kind of an access that is, immediately deletes it. More specifically, the first access is the .add, the second access is another element's .add or this or another element's .remove.
Because of this, each .add and .remove call causes, on average, a single access, which is why it's O(1).
Bit of a convoluted and verbose explanation, but I hope it's clear
*I didn't argue why the .minimum function is O(1) because I believe that's trivial