C++ algorithm: std::pop_heap Function Template

C++ std::pop_heap

The std::pop_heap function in C++ removes the largest (or smallest, for a min-heap) element from a heap and places it at the end of the range. The heap property is maintained for the remaining elements in the range [first, last-1).

This function works in conjunction with std::make_heap, std::push_heap, and std::sort_heap to manage heaps efficiently.

---

Syntax of std::pop_heap

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

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

Parameters of std::pop_heap

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

---

Return Value of std::pop_heap

This function does not return any value. It rearranges the elements in the range so that the largest (or smallest) element is at last-1, and the remaining range [first, last-1) satisfies the heap property.

---

Examples for std::pop_heap

Example 1: Basic Usage of std::pop_heap

This example demonstrates removing the largest element from 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());

    std::cout << "Initial heap: ";
    for (int n : heap) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    // Remove the largest element from the heap
    std::pop_heap(heap.begin(), heap.end());
    int largest = heap.back();
    heap.pop_back();

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

    std::cout << "Popped element: " << largest << 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::pop_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 to satisfy the max-heap property.
   • After this operation, the largest element is at the front of the vector (heap[0]).
4. Display the initial heap:
   • The program uses a for loop to iterate over the elements of the vector and prints the initial heap.
   • The output for the initial heap is: "Initial heap: 20 10 15".
5. Remove the largest element:
   • The function std::pop_heap moves the largest element (heap[0]) to the end of the vector while maintaining the heap structure for the remaining elements.
   • The largest element is then retrieved using heap.back() and removed from the vector using heap.pop_back().
6. Display the heap after removal:
   • The program uses another for loop to print the elements of the heap after the removal operation.
   • The output is: "Heap after pop_heap: 15 10".
7. Display the removed element:
   • The removed largest element is stored in the variable largest and is printed to the console.
   • The output is: "Popped element: 20".

Output:

Initial heap: 20 10 15
Heap after pop_heap: 15 10
Popped element: 20

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

This example demonstrates removing the smallest element from 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);

    std::cout << "Initial min-heap: ";
    for (int n : heap) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    // Remove the smallest element from the heap
    std::pop_heap(heap.begin(), heap.end(), min_heap);
    int smallest = heap.back();
    heap.pop_back();

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

    std::cout << "Popped element: " << smallest << std::endl;

    return 0;
}

Output:

Initial min-heap: 20 30 25
Min-heap after pop_heap: 25 30
Popped element: 20

Exception Handling in std::pop_heap

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

    try {
        // Attempt to remove the largest element with a faulty comparison function
        std::pop_heap(heap.begin(), heap.end(), faulty_compare);
        heap.pop_back(); // Remove the last element after pop_heap
    } catch (const std::exception& e) {
        std::cerr << "Exception caught: " << e.what() << std::endl;
    }

    return 0;
}

Output:

Exception caught: Comparison involving 15 is not allowed.