C++ algorithm: std::push_heap Function Template

C++ std::push_heap

The std::push_heap function in C++ adds a new element to a heap, ensuring that the container satisfies the heap property. The function assumes that the range [first, last-1) is already a valid heap, and it reorders the elements to include last-1 in the heap.

This function is commonly used with std::make_heap, std::pop_heap, and std::sort_heap for heap management.

---

Syntax of std::push_heap

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

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

Parameters of std::push_heap

Parameter	Description
first, last	Random access iterators defining the range of the heap. The element at last-1 is added to the heap.
comp (optional)	A binary comparison function that defines the order of elements. Defaults to <.

---

Return Value of std::push_heap

This function does not return any value. It reorders the elements in the range [first, last) so that they satisfy the heap property.

---

Examples for std::push_heap

Example 1: Basic Usage of std::push_heap

This example demonstrates adding an element to a max-heap:

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

int main() {
    std::vector<int> heap = {10, 20, 15};
    std::make_heap(heap.begin(), heap.end());

    // Add a new element to the heap
    heap.push_back(25);
    std::push_heap(heap.begin(), heap.end());

    std::cout << "Heap after push_heap: ";
    for (int n : heap) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

Explanation:

1. Include necessary headers:
   • <iostream>: Used for input/output operations.
   • <algorithm>: Includes functions for heap operations, such as std::make_heap and std::push_heap.
   • <vector>: Used for the std::vector container.
2. Initialize a vector:
   • A vector named heap is initialized with the elements {10, 20, 15}.
3. Convert the vector into a heap:
   • The function std::make_heap rearranges the elements in the vector so that it satisfies the properties of a max-heap.
   • After this operation, the largest element is at the front of the vector (heap[0]).
4. Add a new element:
   • A new element 25 is added to the end of the vector using heap.push_back(25).
5. Maintain the heap structure:
   • The function std::push_heap is used to adjust the heap structure after adding the new element.
   • It ensures that the newly added element is moved to the correct position to maintain the max-heap property.
6. Output the heap:
   • The program uses a for loop to iterate over the elements of the vector and prints them in their current order.
   • The output is: "Heap after push_heap: 25 20 15 10", showing that the max-heap property is preserved.

Output:

Heap after push_heap: 25 20 15 10

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

This example demonstrates adding an element to 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> heap = {20, 30, 25};
    std::make_heap(heap.begin(), heap.end(), min_heap);

    // Add a new element to the heap
    heap.push_back(15);
    std::push_heap(heap.begin(), heap.end(), min_heap);

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

    return 0;
}

Output:

Min-Heap after push_heap: 15 20 25 30

Exception Handling in std::push_heap

The std::push_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> heap = {15, 20, 10};
    std::make_heap(heap.begin(), heap.end());

    try {
        // Add a new element to the heap
        heap.push_back(25);
        std::push_heap(heap.begin(), heap.end(), faulty_compare);
    } catch (const std::exception& e) {
        std::cerr << "Exception caught: " << e.what() << std::endl;
    }

    return 0;
}

Output:

Exception caught: Comparison involving 15 is not allowed.