C++ algorithm: std::is_heap Function Template

C++ std::is_heap

The std::is_heap function in C++ checks if the elements in a range satisfy the heap property. For a max-heap, every parent node must be greater than or equal to its child nodes, and for a min-heap, every parent node must be less than or equal to its child nodes.

---

Syntax of std::is_heap

template <class RandomAccessIterator>
bool is_heap(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class Compare>
bool is_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Parameters of std::is_heap

Parameter	Description
first, last	Random access iterators defining the range to check. The range is [first, last).
comp (optional)	A binary comparison function that defines the order of elements. Defaults to <.

---

Return Value of std::is_heap

Returns true if the elements in the range satisfy the heap property. Returns false otherwise.

---

Examples for std::is_heap

Example 1: Basic Usage of std::is_heap

This example demonstrates checking whether a vector satisfies the heap property:

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

int main() {
    std::vector<int> nums = {40, 30, 20, 10, 15};

    if (std::is_heap(nums.begin(), nums.end())) {
        std::cout << "The range is a valid max-heap." << std::endl;
    } else {
        std::cout << "The range is not a valid max-heap." << std::endl;
    }

    return 0;
}

Explanation:

1. Include necessary headers:
   • <iostream>: Used for input/output operations.
   • <algorithm>: Includes the std::is_heap function to check heap validity.
   • <vector>: Used for the std::vector container.
2. Initialize a vector:
   • A vector named nums is initialized with the elements {40, 30, 20, 10, 15}.
   • This vector represents a range of integers that may or may not satisfy the max-heap property.
3. Check if the range is a valid heap:
   • The function std::is_heap checks if the elements in the range [nums.begin(), nums.end()) satisfy the max-heap property.
   • In a max-heap, each parent node is greater than or equal to its child nodes.
4. Output the result:
   • If the vector satisfies the max-heap property, the function returns true, and the program outputs: "The range is a valid max-heap.".
   • If the vector does not satisfy the max-heap property, the function returns false, and the program outputs: "The range is not a valid max-heap.".

Output:

The range is a valid max-heap.

Example 2: Using a Custom Comparison Function for std::is_heap

This example demonstrates checking whether a vector satisfies the heap property for a min-heap using a custom comparison function:

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

bool min_heap(int a, int b) {
    return a > b;
}

int main() {
    std::vector<int> nums = {10, 20, 15, 30, 40};

    if (std::is_heap(nums.begin(), nums.end(), min_heap)) {
        std::cout << "The range is a valid min-heap." << std::endl;
    } else {
        std::cout << "The range is not a valid min-heap." << std::endl;
    }

    return 0;
}

Output:

The range is a valid min-heap.

Exception Handling in std::is_heap

The std::is_heap function does not throw exceptions on its own. However, the comparison function passed as an argument may throw exceptions, which can be caught and handled appropriately.

Example 1: Exception in Custom Comparison Function

This example demonstrates how exceptions in a custom comparison function are handled:

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

bool faulty_compare(int a, int b) {
    if (a == 15 || b == 15) {
        throw std::runtime_error("Comparison involving 15 is not allowed.");
    }
    return a < b;
}

int main() {
    std::vector<int> nums = {40, 30, 15, 10, 20};

    try {
        if (std::is_heap(nums.begin(), nums.end(), faulty_compare)) {
            std::cout << "The range is a valid heap." << std::endl;
        } else {
            std::cout << "The range is not a valid heap." << std::endl;
        }
    } catch (const std::exception& e) {
        std::cerr << "Exception caught: " << e.what() << std::endl;
    }

    return 0;
}

Output:

Exception caught: Comparison involving 15 is not allowed.