C++ std::sort_heap

The std::sort_heap function in C++ sorts the elements of a heap into ascending order. The function assumes the range [first, last) is a valid heap. After the operation, the elements in the range are sorted, and the heap property is no longer maintained. This function works with random access iterators and is used in conjunction with std::make_heap and std::pop_heap to manage heaps.

Syntax of std::sort_heap

</>
Copy
template <class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last);

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

Parameters of std::sort_heap

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

Return Value of std::sort_heap

This function does not return any value. It rearranges the elements in the range [first, last) in ascending order.

Examples for std::sort_heap

Example 1: Basic Usage of std::sort_heap

This example demonstrates sorting a max-heap into ascending order:

</>
Copy
#include <iostream>
#include <algorithm>
#include <vector>

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

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

    // Sort the heap into ascending order
    std::sort_heap(heap.begin(), heap.end());

    std::cout << "Sorted 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 like std::make_heap and std::sort_heap for heap operations.
    • <vector>: Used for the std::vector container.
  2. Initialize a vector:
    • A vector named heap is initialized with the elements {40, 30, 15, 10, 20}.
    • The elements represent 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 max-heap property.
    • In a max-heap, the largest element is placed at the front of the vector (heap[0]).
  4. Display the heap before sorting:
  5. Sort the heap:
    • The function std::sort_heap sorts the elements in ascending order while maintaining the heap structure during the process.
    • After this operation, the heap property is no longer valid, as the elements are fully sorted in ascending order.
  6. Display the sorted heap:
    • The program uses another for loop to print the elements of the vector after sorting.
    • The output is: "Sorted heap: 10 15 20 30 40".

Output:

Heap before sort_heap: 40 30 15 10 20
Sorted heap: 10 15 20 30 40

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

This example demonstrates sorting a min-heap in descending order using a custom comparison function:

</>
Copy
#include <iostream>
#include <algorithm>
#include <vector>

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

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

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

    // Sort the heap in descending order
    std::sort_heap(heap.begin(), heap.end(), min_heap);

    std::cout << "Sorted heap in descending order: ";
    for (int n : heap) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

Output:

Min-Heap before sort_heap: 10 20 15 30 40
Sorted heap in descending order: 40 30 20 15 10

Exception Handling in std::sort_heap

The std::sort_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:

</>
Copy
#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 = {40, 30, 15, 10, 20};
    std::make_heap(heap.begin(), heap.end());

    try {
        // Attempt to sort the heap with a faulty comparison function
        std::sort_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.