Binary heap pop-push operation using `pop_heap`

Runtimes C++
1

I’ve been using std::pop_heap for a combined pop-push operation by appending a new element at the end, then calling std::pop_heap and then removing the last element. It used to work just fine, and it still works in the latest libstdc++ but not the latest libc++.

I used this as an optimization, relying on what cppreference.com says about it:

Swaps the value in the position first and the value in the position last-1 and makes the subrange [first, last-1) into a heap . This has the effect of removing the first element from the heap defined by the range [first, last) .

But now that I found it to break, I couldn’t really find any confirmation as to what the actual standard says. Does anybody know? I’d appreciate the help.

I looked into the algorithms in both libc++ and libstdc++, and they seem to both work in a very similar way, except I think (as far as I could understand) that the GNU one sifts down excluding the last element, but the LLVM one includes all elements, and in result it can push that last element up when doing the initial sifting…

This should be relatively easy to fix, but of course the real question is whether it the precondition of std::pop_heap is that [first, last) is a valid heap, or whether we only need [first, last - 1) (which is what I’ve been doing).

Another question is: does my pop-push optimization make sense? At the first glance: yes; but since that “bottom-up heapsort” strategy is used (first sift the hole all the way down, and then sift up), and the new element does not necessarily belong at the bottom, maybe it is less of an optimization.

I plan to do some benchmarking soon, but I’d love to know what y’all think, especially on the standard/correctness issue.

2

[pop.heap] is the relevant part, and it says that [first, last) has to be a heap. I don’t know enough about the algorithm itself to be able to tell you if the optimization makes sense, but as a general rule, benchmarking is the only way to be sure what you expect actually happens.

3

[pop.heap] is the relevant part, and it says that [first, last) has to be a heap.

I see. Thanks a lot, I appreciate you finding it; I’ve never actually had to look up details in the standard itself, and I had a hard time finding it – the official website just wants you to buy it apparently.

I don’t know enough about the algorithm itself to be able to tell you if the optimization makes sense, but as a general rule, benchmarking is the only way to be sure what you expect actually happens.

Yep, agreed. Given the standard’s definition, I’ll have to change my implementation either way, but I’ll probably also measure to find out if there’s performance regression.

4

In case anyone is interested, I did benchmark this a bit; I won’t bore you with numbers because I’d have to spend a long time explaining the exact scenario and setup, but suffice it to say that calling pop+push was significantly enough slower that I decided to write my own sift down function, and it actually is faster than the STL one in my scenario (the sifted down elements are not necessarily leaves). This was benchmarked on GCC 12 because I had issues linking Google benchmark lib with Clang, but my understanding is that LLVM version of the algorithm is very similar to the one implemented in GNU stdlib.