Heap in C++ STL | make_heap(), push_heap(),pop_heap(), sort_heap(), is_heap, is_heap_until()

The C++ STL <algorithm> header provides a set of functions for working with binary heaps, which are data structures commonly used in heapsort and priority queues. These functions include make_heap(), push_heap(), pop_heap(), sort_heap(), is_heap(), and is_heap_until(). These functions allow you to create and manipulate binary heaps efficiently.

Here’s a brief overview of each of these functions:

1. make_heap():

• make_heap() is used to convert a random-access container (like a vector or an array) into a valid max-heap or min-heap.
• By default, it creates a max-heap. To create a min-heap, you can provide a custom comparison function.

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

 int main() {
     std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
     std::make_heap(v.begin(), v.end()); // Convert to max-heap

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

     return 0;
 }

2. push_heap():

• push_heap() adds a new element to the heap while maintaining the heap property.
• It assumes that the container already represents a valid heap, and it adds the new element to the correct position.

 std::vector<int> v = {3, 1, 4, 1, 5};
 v.push_back(2);           // Add a new element
 std::push_heap(v.begin(), v.end());

 // Now, v is a max-heap with the new element included.

3. pop_heap():

• pop_heap() rearranges the elements in a heap such that the largest (for max-heap) or the smallest (for min-heap) element is moved to the end of the container.
• After calling pop_heap(), you typically use pop_back() to remove the last element from the container, effectively removing the largest or smallest element.

 std::pop_heap(v.begin(), v.end()); // Move the largest element to the end
 v.pop_back();                      // Remove the largest element

4. sort_heap():

• sort_heap() is used to sort the elements of a heap (max-heap or min-heap) in ascending order.
• After calling sort_heap(), the container represents a sorted sequence, but it may no longer be a valid heap.

 std::sort_heap(v.begin(), v.end()); // Sort the heap

5. is_heap():

• is_heap() checks if a given range is a valid heap (max-heap or min-heap).
• It returns true if the range is a valid heap, otherwise false.

 bool isHeap = std::is_heap(v.begin(), v.end()); // Check if it's a heap

6. is_heap_until():

• is_heap_until() returns an iterator to the first element in the range that violates the heap property.
• If the entire range satisfies the heap property, it returns last.

 auto firstNonHeap = std::is_heap_until(v.begin(), v.end()); 
 // Find the first element violating the heap property

These functions are useful when working with heaps and can simplify the implementation of algorithms like heapsort and priority queues. They provide efficient ways to maintain and manipulate heap data structures.