C++ algorithm: std::is_heap_until Function Template

C++ std::is_heap_until

The std::is_heap_until function in C++ checks how far a range satisfies the heap property. It returns an iterator to the first element in the range that violates the heap property. If the entire range satisfies the heap property, the function returns last.

---

Syntax of std::is_heap_until

template <class RandomAccessIterator>
RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last);

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

Parameters of std::is_heap_until

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_until

Returns an iterator to the first element in the range [first, last) that violates the heap property. If the entire range satisfies the heap property, the function returns last.

---

Examples for std::is_heap_until

Example 1: Basic Usage of std::is_heap_until

This example demonstrates checking how far a vector satisfies the heap property:

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

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

    auto it = std::is_heap_until(nums.begin(), nums.end());

    std::cout << "Heap property is maintained until element: " << (it - nums.begin()) << std::endl;

    return 0;
}

Explanation:

1. Include necessary headers:
   • <iostream>: Used for input/output operations.
   • <algorithm>: Includes the std::is_heap_until function to check where the heap property is violated.
   • <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, 25}.
   • This vector represents a range of integers that may partially satisfy the max-heap property.
3. Find the point where the heap property is violated:
   • The function std::is_heap_until checks the range [nums.begin(), nums.end()) to determine where the heap property is no longer maintained.
   • It returns an iterator pointing to the first element that violates the max-heap property.
   • If the entire range satisfies the heap property, the function returns nums.end().
4. Calculate the position:
   • The position of the violating element is determined by subtracting nums.begin() from the iterator returned by std::is_heap_until.
5. Output the result:
   • The program prints the position where the heap property is no longer maintained.
   • If the heap property is valid for the entire range, the output will indicate the size of the vector.
   • For the given input, the output is: "Heap property is maintained until element: 5", as the first five elements satisfy the max-heap property, but the last element (25) violates it.

Output:

Heap property is maintained until element: 5

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

This example demonstrates checking 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};

    auto it = std::is_heap_until(nums.begin(), nums.end(), min_heap);

    std::cout << "Min-heap property is maintained until element: " << (it - nums.begin()) << std::endl;

    return 0;
}

Output:

Min-heap property is maintained until element: 5

---

Exception Handling in std::is_heap_until

The std::is_heap_until 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 {
        auto it = std::is_heap_until(nums.begin(), nums.end(), faulty_compare);
        std::cout << "Heap property is maintained until element: " << (it - nums.begin()) << 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.