Knowledge baseExam Center
ENEnglish
Choose language13

CKTIS / C++

std::push_heap — adding an element to a heap

std::push_heap restores the heap property after one element has been appended to a range. It does not grow the container: the new element must already be at last - 1, and the preceding part of the range must already be a valid heap.

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

Syntax

#include <algorithm>

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

std::push_heap, declared in <algorithm>, incorporates the element at last - 1 into the heap spanning [first, last). It does not append an element to the container and returns void. The usual sequence is push_back, followed by std::push_heap using current iterators.

Before the call, [first, last - 1) must already be a heap under the same ordering. The range must contain at least the new element; do not call the algorithm on an empty range. To build a heap from arbitrary data, use std::make_heap, not a single call to std::push_heap.

The default comparison produces a max-heap: the largest element is at the beginning. The overload taking comp changes the ordering; std::greater<int>{} produces a min-heap. The comparator must define a strict weak ordering and match the ordering of the existing heap. A heap need not be sorted.

Random-access iterators are required, and elements must support swapping, move construction, and move assignment. The number of comparisons is O(log N), where N = last - first; the preceding push_back has a separate cost. In the example, {9, 5, 7} is already a heap, so after appending 12, one call suffices to restore the heap property.

Examples

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

int main() {
    std::vector<int> heap{9, 5, 7};
    heap.push_back(12);
    std::push_heap(heap.begin(), heap.end());

    std::cout << "top: " << heap.front() << '\n';
    std::cout << "size: " << heap.size() << '\n';
    std::cout << "is_heap: " << std::boolalpha
              << std::is_heap(heap.begin(), heap.end()) << '\n';
}

Result

top: 12
size: 4
is_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