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.