Why do both insertion and extraction into/from a std::priority_queue take logarithmic time?
<blockquote>
<p>A [<a href="http://en.cppreference.com/w/cpp/container/priority_queue" rel="nofollow noreferrer"><code>std::priority_queue</code></a>] is a container adaptor that provides constant time lookup of the largest (by default) element, at the expense of <strong>logarithmic insertion and extraction</strong>.</p>
</blockquote>
<p>Why is that? I think the sorting either happens on insertion or extraction.
For example, if the sorting happens on insertion and the internal container remains sorted, wouldn't the extraction be able to happen in constant time? The top element to be removed is know and so is the next smaller one.</p>
<p>However, both <a href="http://en.cppreference.com/w/cpp/container/priority_queue/push" rel="nofollow noreferrer"><code>std::priority_queue::push</code></a> and <a href="http://en.cppreference.com/w/cpp/container/priority_queue/pop" rel="nofollow noreferrer"><code>std::priority_queue::pop</code></a> mention in their complexity descriptions:</p>
<blockquote>
<h2>Complexity</h2>
<p>Logarithmic number of comparisons</p>
</blockquote>
<p>Why would <strong>both</strong> have to perform comparisons? With an internal container that stays sorted, extraction should be easy or vice versa, with sorting upon extraction, insertion should be easy.</p>
<p>I guess my assumption about when and how the sorting happens (or if there's any sorting happening at all) is just wrong. Could somebody please shed some light on this?</p>