Knowledge baseExam Center
ENEnglish
Choose language13

CKTIS / C++

std::is_heap — checking the heap property

std::is_heap checks whether a range satisfies the heap property without changing its elements. By default it recognizes a max-heap; a custom comparator lets you check another ordering, such as a min-heap.

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

Syntax

#include <algorithm>
std::is_heap(first, last)
std::is_heap(first, last, comp)

std::is_heap, declared in <algorithm>, returns bool after checking the range [first, last). It requires a valid range and random-access iterators, such as those of std::array or std::vector. It does not build or repair a heap and does not rearrange elements. An empty or single-element range satisfies the condition.

For every child index i > 0, the parent index is (i - 1) / 2, using integer division. The heap condition requires comp(parent, child) to be false. The default comparison std::less{} gives a max-heap for numbers: a parent is not smaller than its child. std::greater<int>{} checks a min-heap. The comparator must define a strict weak ordering; use the same ordering that was used to build the heap.

A heap need not be sorted: siblings have no required relative order. Checking has linear complexity in the number of elements. The result is equivalent to testing std::is_heap_until(first, last, comp) == last; that other function helps locate the first violation. Use std::make_heap to build a heap.

The example first recognizes a max-heap, then rejects it as a min-heap, and finally detects a violation against the parent value 5 after assigning values[3] = 10. The shown overloads without an execution policy are constexpr; execution-policy overloads also exist. This entry targets C++23. The source is an evolving standard draft, and the repository compiler flag does not attest the production runtime.

Examples

#include <algorithm>
#include <array>
#include <functional>
#include <iostream>

int main() {
    std::array<int, 5> values{9, 5, 8, 1, 3};
    std::cout << std::boolalpha;
    std::cout << std::is_heap(values.begin(), values.end()) << '\n';
    std::cout << std::is_heap(values.begin(), values.end(),
                              std::greater<int>{}) << '\n';
    values[3] = 10;
    std::cout << std::is_heap(values.begin(), values.end()) << '\n';
}

Result

true
false
false

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