Knowledge baseExam Center
ENEnglish
Choose language13

CKTIS / C++

std::pop_heap — move the heap root to the end

std::pop_heap moves the root of a nonempty heap to the end of the range and restores the heap in the remaining prefix. It does not erase a container element. For std::vector, pop_back() removes the extracted element only if the heap range ends at the end of the vector.

Version: C++23; repository compiler flag, production runtime not attested

Syntax

#include <algorithm>

std::pop_heap(first, last);
std::pop_heap(first, last, comp);

std::pop_heap, declared in <algorithm>, operates on [first, last). It moves the original root to last - 1 and restores a heap in [first, last - 1). By default, the root is the largest element. The overload taking comp uses the supplied ordering; both overloads return void.

The range must already be a nonempty heap under the same ordering. Iterators must support random access, and elements must support swapping, move construction, and move assignment. The comparator must define a strict weak ordering. Calling it on an empty range or a range that is not a heap violates its preconditions.

The algorithm does not shrink the container. After the call, read the extracted element through *(last - 1). For a std::vector, use back() to read it and pop_back() to remove it only if last equals the vector's end(). If the range ends earlier, those calls would read and remove a different element. Before another call, exclude the previously extracted element from the range. The comparison count is at most 2 * log2(N), where N = last - first.

The example builds a heap using std::make_heap and prints only guaranteed results, not the heap's internal arrangement. The displayed code was run unchanged, and its standard output exactly matched the supplied output. The source is an evolving working draft, not frozen C++23 text.

Examples

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

int main() {
    std::vector<int> values{4, 1, 7, 3};
    std::make_heap(values.begin(), values.end());

    std::pop_heap(values.begin(), values.end());
    std::cout << "extracted=" << values.back() << '\n';
    std::cout << "size_before=" << values.size() << '\n';

    values.pop_back();
    std::cout << "size_after=" << values.size() << '\n';
    std::cout << "next=" << values.front() << '\n';
    std::cout << "heap=" << std::boolalpha
              << std::is_heap(values.begin(), values.end()) << '\n';
}

Result

extracted=7
size_before=4
size_after=3
next=4
heap=true

The displayed code and declared result were verified in an isolated environment using the method recorded in the verification evidence for this exact version.

Sources