C++ algorithm: std::make_heap Function Template

C++ std::make_heap

The std::make_heap function in C++ transforms a range of elements into a valid heap. A heap is a binary tree structure where each parent node is greater than or equal to its child nodes in a max-heap, or smaller than or equal to its child nodes in a min-heap. This function works with random access iterators and is often used with other heap-related functions like std::push_heap and std::pop_heap.

---

Syntax of std::make_heap

template <class RandomAccessIterator>
void make_heap(RandomAccessIterator first, RandomAccessIterator last);

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

Parameters of std::make_heap

Parameter	Description
first, last	Random access iterators defining the range of elements to transform into a heap. The range is [first, last).
comp (optional)	A binary comparison function that defines the order of elements. Defaults to <, creating a max-heap.

---

Return Value of std::make_heap

This function does not return any value. It rearranges the elements in the range [first, last) to satisfy the heap property.

---

Examples for std::make_heap

Example 1: Basic Usage of std::make_heap

This example demonstrates how to create a max-heap from a vector:

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

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

    // Transform the vector into a max-heap
    std::make_heap(nums.begin(), nums.end());

    std::cout << "Max-Heap: ";
    for (int n : nums) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

Explanation:

1. Include necessary headers:
   • <iostream>: Used for input/output operations.
   • <algorithm>: Includes the std::make_heap function for heap operations.
   • <vector>: Used for the std::vector container.
2. Initialize a vector:
   • A vector named nums is initialized with the elements {10, 20, 15, 30, 40}.
   • This vector represents an unsorted collection of integers.
3. Transform the vector into a max-heap:
   • The function std::make_heap rearranges the elements of the vector to satisfy the properties of a max-heap.
   • In a max-heap, the largest element is placed at the root (index 0), and the child nodes are smaller than their parent nodes.
4. Display the max-heap:
   • The program uses a for loop to iterate over the elements of the vector and prints them in their heapified order.
   • While the order may not be entirely sorted, the max-heap property ensures the largest element is at the front.
   • The output is: "Max-Heap: 40 30 15 10 20".

Output:

Max-Heap: 40 30 15 10 20

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

This example demonstrates how to create a min-heap using a custom comparison function:

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

bool min_heap(int a, int b) {
    return a > b; // Reverse comparison for a min-heap
}

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

    // Transform the vector into a min-heap
    std::make_heap(nums.begin(), nums.end(), min_heap);

    std::cout << "Min-Heap: ";
    for (int n : nums) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

Output:

Min-Heap: 10 20 15 30 40

Exception Handling in std::make_heap

The std::make_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 == 20 || b == 20) {
        throw std::runtime_error("Comparison involving 20 is not allowed.");
    }
    return a < b;
}

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

    try {
        // Attempt to create a heap with a faulty comparison function
        std::make_heap(nums.begin(), nums.end(), faulty_compare);
    } catch (const std::exception& e) {
        std::cerr << "Exception caught: " << e.what() << std::endl;
    }

    return 0;
}

Output:

Exception caught: Comparison involving 20 is not allowed.