C++ Basics: Remove the Largest Heap Value in Two Steps

Pair std::pop_heap with pop_back to remove the maximum element from a vector heap.

Prepare a scratch directory

Tested on Linux x86_64 with GCC 14.2.0. Install a C++20-capable compiler and standard-library development headers, with g++ on PATH. You also need Bash, a text editor, and the mktemp, rm, and rmdir utilities. No third-party library is required.

Keep the same terminal open. Stop if setup fails, before saving the source:

start_directory="$PWD"
work_directory="$(mktemp -d)" || exit 1
cd -- "$work_directory" || exit 1

Run the example

Save this as heap-pop-removal-demo.cpp:

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> pending{4, 9, 2};
    std::make_heap(pending.begin(), pending.end());
    pending.push_back(7);
    std::push_heap(pending.begin(), pending.end());
    std::pop_heap(pending.begin(), pending.end());
    const int taken = pending.back();
    pending.pop_back();
    std::cout << "Taken: " << taken << '\n';
    std::cout << "Next: " << pending.front() << '\n';
    std::cout << "Remaining: " << pending.size() << '\n';
}

Compile and run it. The program runs only after compilation succeeds:

g++ -std=c++20 -Wall -Wextra -Werror -pedantic heap-pop-removal-demo.cpp -o heap-pop-removal-demo &&
./heap-pop-removal-demo

Observed output:

Taken: 9
Next: 7
Remaining: 3

Read the result

The largest value, 9, is moved to the final position by pop_heap. pop_back then removes that element from the vector. The remaining prefix is a heap whose maximum is 7. Insertion likewise requires appending the value and restoring the heap with push_heap.

Apply it carefully

pop_heap rearranges elements but does not change the container size. Check that a heap is nonempty before popping, and check again before reading front() after removal. Use the same comparison for make_heap, push_heap, and pop_heap. A heap is not a fully sorted sequence, so avoid depending on its internal array layout. std::priority_queue can hide these maintenance steps when direct vector access is unnecessary.

The C++ working draft describes the relevant rules. This example builds in C++20 mode; the current working draft also documents later additions.

Clean up

Remove only the source and executable created here, then return to the starting directory:

rm -- heap-pop-removal-demo.cpp heap-pop-removal-demo
cd -- "$start_directory" || exit 1
rmdir -- "$work_directory"
unset start_directory work_directory

If the directory is not empty, inspect its remaining contents before removing anything else.

Acknowledgements

This post was created with assistance from AI.