On Sat, Jan 17, 2026 at 3:19 PM Alexey Sidorin via Std-Proposals <
std-proposals_at_[hidden]> wrote:

> Hello everyone,
>
> I would like to propose adding extract_top() method to
> std::priority_queue backed by a set of freestanding functions in
> <algorithm> header.
>

You propose:
- T std::priority_queue<T>::extract_top()
- T std::extract_heap_top(It first, It last, Compare c);

(1) The existing heap algorithms are always named with the suffix `_heap`;
you propose a name with `_heap_` on the inside. I don't like that. The
natural name given your nomenclature would be simply `std::extract_heap`.
(2) But I suggest that you should do what I did in this 2023 blog post
<https://quuxplusone.github.io/blog/2023/03/01/priority-queue-displace-top/>:
The name should be
- T std::priority_queue<T>::displace_top()
by analogy to `emplace`. Emplace constructs a new element; displace
(conceptually) destroys that element, returning its value. Notice that
priority_queue::emplace does not *literally* construct a new element at
c[0]; there's already an element there, which it must assign into; likewise
priority_queue::displace wouldn't *literally* destroy the element at c[0];
it's the element at the tail of the container that's destroyed. But this is
the correct level of abstraction for priority_queue.

(3) These next two items turn out to be me talking myself into agreeing
with you — but I had to work it out myself. I think your paper should
include this reasoning, if you can condense it into something that's both
short *and* convincing.
At first glance, you don't need a new free algorithm at all. To implement
`priority_queue::displace_top`, it suffices to call `T ret =
std::move(c.front())` followed by `std::pop_heap` followed by `return ret`.
Your §2 explains why actually `pop_heap` isn't as efficient as it could be
— *but* I believe it's very easy to skim over this paragraph and not
realize the point it's making. You write:

> Another issue with top()& pop() approach is that pop() uses
> std::pop_heap() + c.pop_back() call pair
> internally. And std::pop_heap() is required to move the top element to the
> sequence end. This can introduce
> stores hard to elide by compilers.

That is, `pop_heap` *swaps* the top element to the bottom (and then
sifts-down the new top element [*]) — that's why your Chromium call-sites
are able to get away with

> std::pop_heap(queue.begin(), queue.end());
> *event = std::move(queue.back());
> queue.pop_back();

Your proposed new free algorithm can do better because it doesn't swap, it
*move-assigns* the top element to the bottom (and then...[*]) Therefore it
leaves `queue.back()` in a moved-from state. Move-assign is likely more
efficient than swap, at least in some cases. [Actually this likely isn't
true, but see (4) for why two wrongs make a right.] Your Chromium callers
can then write:

> *event = std::move(queue.top());
> std::extract_top_heap(queue.begin(), queue.end());
> queue.pop_back();

...Oh, wait, no they probably can't, because the moved-from queue[0] is no
longer in heap order; we've violated the heap invariant. That's why
`extract_top_heap` (or `displace_heap`, as I'd like to call it) needs to
*return* the element, so that it can receive a range in heap-order and
return a range still in heap-order, without any moved-from "holes" at the
top in either case.

(4) Notice the [*]s above. I don't think it's obvious why your thing would
be more efficient than just doing pop_heap... and part of that is that it's
not obvious what *pop_heap* is actually doing. As you can see from your own
patch <https://github.com/a-sid/llvm-project/pull/1/files>, pop_heap (at
least on libc++) uses the "heapsort with bounce" algorithm due to Floyd
<https://reviews.llvm.org/D118003>, which means that what pop_heap is
currently doing (on libc++) is *not* "sifting down the new element" by a
series of swaps, but rather:
- Pull out (that is, move-construct from) the top, leaving a hole.
- Bubble that hole down to some leaf, by repeatedly swapping the hole (that
is, move-assigning) with its bigger child.
- If the hole didn't end up at the rightmost leaf, then swap the hole with
(that is, move-assign from) the rightmost leaf, and bubble that value
upward by swapping with its parent.
- Finally, *move-assign from* the old top element *into the rightmost leaf.*
Your new free algorithm is doing:
- Pull out (that is, move-construct from) the top, leaving a hole.
- Bubble that hole down to some leaf, by repeatedly swapping the hole (that
is, move-assigning) with its bigger child.
- If the hole didn't end up at the rightmost leaf, then swap the hole with
(that is, move-assign from) the rightmost leaf, and bubble that value
upward by swapping with its parent.
- Finally, *return* the old top element.
So, your new algorithm permits us to — and *your patch actually does* —
implement `std::pop_heap` as:
    *std::prev(last) = std::extract_top_heap(first, last);

(5) Shouldn't you, then, re-specify `priority_queue<T>::pop()` to do
`extract_top_heap/displace_heap` instead of `pop_heap`? It's just going to
`pop_back()` anyway, so it shouldn't be forced to pay for that extra
assignment to `c.back()` anymore.

(6) In fact, maybe `.pop()` shouldn't be forced to pay for
`extract_top_heap/displace_heap`'s *returning* the T which
priority_queue<T>::pop() is just going to discard anyway! However, short
of complicating the precondition on `extract_top_heap` (i.e. "the range
must be in heap order, except for the first element, which is assumed to be
bigger than all the others but we don't check it so it doesn't actually
need to be"), I can't think of a good way to deal with this. So you could
defend the current specification by pointing out that returning T costs us
only a single extra move-construction and destruction, compared to the
ideal case. ...Wait, that's not a defense. Hm.

(7) Nitpick: You write
    iterator_traits_t<RandomAccessIterator>::value_type
    iterator_traits<iterator_t<R>>::value_type
but for consistency and brevity you should write
    iter_value_t<RandomAccessIterator>
    range_value_t<R>
instead.

(8) In short, I would counter-propose something like this (plus Ranges
overloads for the free algorithms, of course):
- T std::displace_heap(It first, It last, Compare c);
    The same as pop_heap, except that it leaves last[-1] in a moved-from
state and returns the old top. Compared to C++26 pop_heap, saves one
move-assign.
- T std::priority_queue<T>::displace_top();
    Implemented in terms of std::displace_heap. Enables using
priority_queue with unique_ptr. This is a big deal.
- void std::foobar_trashing_pop_heap(It first, It last, Compare c);
    The same as pop_heap, except that it leaves last[-1] in a moved-from
state. Compared to C++26 pop_heap, saves one each of move-construct,
move-assign, destroy.
- void std::priority_queue<T>::pop();
<https://eel.is/c++draft/priqueue.members#6>
    Re-specify in terms of std::foobar_trashing_pop_heap. Compared to
C++26 pop, saves one each of move-construct, move-assign, destroy.

my $.02,
–Arthur