C++ Heap

In C++, a heap serves as a tree-structured data arrangement primarily employed for priority queues and the effective retrieval of the maximum or minimum item. The C++ STL provides various predefined functions for managing heaps, including makeheap, pushheap, popheap, sortheap, isheap, and isheap_until.

The heap, also referred to as the free store, is responsible for managing memory allocation dynamically during a program's execution. Memory is acquired from this memory space using operators like new or malloc. When utilizing operators such as new or malloc, memory is sourced from this specific memory segment.

Types of Heaps in C++

The heap in C++ can be classified primarily into two categories:

• ✅ Maximum Heap
• ✅ Minimum Heap

Sometimes, these data structures are commonly used in different kinds of algorithms, like priority queues, sorting algorithms, and various graph algorithms. The functionalities of this framework consist of functions related to heaps, which can be configured to function as either min-heaps or max-heaps based on the comparators.

Max-Heap

In C++, a Max-Heap represents a form of binary heap where the value in each node is greater than or equal to the values of its child nodes. Essentially, the highest value resides at the root, and all sub-trees of the max-heap adhere to this property as well.

Characteristics of Max-Heap

Several characteristics of the Max-heap in C++ are as follows:

• ✅ The largest element is at the top of the heap because the heap data structure maintains the property that parent nodes' keys are larger than its child nodes' keys.
• ✅ In other words, for every parent node in a binary tree, its value is greater than or equal to any of its children nodes.
• ✅ The heap is constructed to incorporate new elements in a way that would not violate the heap property.

Use Cases of Max-Heap

Several applications of the Max-heap in C++ include:

• ✅ : Priority Queues: Max-heaps are commonly used in scenarios where priority queues are required. Unlike binary search trees, nodes at the same level in a max-heap are not ordered. The root node always holds the element with the highest priority in a max-heap.
• ✅ : Heap Sort: This technique involves organizing data in descending order using a max-heap. The array is sorted by iteratively removing the largest element from the heap and appending it to the end of the array.

C++ Max-heap Example

Let's consider an instance to demonstrate the max-heap concept in C++.

Example

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;  //using standard namespace

int main() {  //Main function

    

    vector<int> data = {10, 20, 15, 30, 40};

    // Creating a max-heap

    make_heap(data.begin(), data.end());

    cout << "Max Heap: ";   //prints the max heap value

    for (int n : data) cout << n << " ";   

    return 0;

}

Output:

Max Heap: 40 30 15 10 20

Explanation

In this illustration, we showcase the process of constructing a max-heap by employing the make_heap function within the STL library. The procedure involves initializing a vector with elements, transforming it into a max-heap configuration where the most significant element occupies the initial position, and subsequently displaying the heapified vector.

Min-Heap

In C++, a Min-Heap represents a set of elements with characteristics akin to a Binary Heap, with the added requirement that the parent node's key must be lesser than or equal to the keys of its children. This structure guarantees that the smallest item is positioned at the top of the heap. Moreover, each sub-tree within the Min-Heap must adhere to this rule, enhancing its effectiveness for various tasks such as accessing or deleting the smallest element.

Characteristics of Min-Heap

Several characteristics of Min-heap in C++ are as follows:

• ✅ In the heap, the smallest element is the one at the root of that heap or the top of the heap.
• ✅ It was also shown that every parent node is less than or equal to the nodes in its children set.
• ✅ The heap is organized in such a way that new items are going to be inserted while maintaining the heap property.

Use Cases

Several scenarios where Min-heap is applied in C++ include:

• ✅ Priority Queues: The initial node of the min-heap consistently holds the minimum priority, making it ideal for priority queues requiring the removal of the element with the lowest priority.
• ✅ Dijkstra's Algorithm: In algorithms such as Dijkstra's shortest path, min-heaps play a crucial role by facilitating the retrieval of the smallest (least expensive) node during each iteration.

C++ Min-Heap Example

To utilize a min-heap in C++, a personalized comparator can be employed to establish the ordering.

Example

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;  //using standard namespace

int main() {   //main function

    

    vector<int> data = {10, 20, 15, 30, 40};    

    // Creating a min-heap using a custom comparator

    make_heap(data.begin(), data.end(), greater<int>());

    cout << "Min Heap: ";

    for (int n : data) cout << n << " ";

    return 0;

}

Output:

Min Heap: 10 20 15 30 40

Explanation

In this instance, we construct a Min-Heap from a vector by employing make_heap along with the greater<int> comparator, guaranteeing that the smallest element is placed at the beginning of the heap. Subsequently, the elements are displayed in their organized heap sequence.

Why Do We Use the Heap in C++?

Here are some reasons why we use heap in C++.

1) Dynamic Size

It implies that if the size of an object or an array cannot be determined during compile time, the heap is utilized to assign memory based on user input or specific conditions.

2) Longer Lifetime

In the C++ programming language, heap memory remains allocated until manually released. This is particularly beneficial when objects need to persist beyond the scope of the function where they are instantiated.

3) Flexible Data Structures

Singly linked lists, trees, graphs, and hash tables, along with other intricate data structures, require heap allocation due to their dynamic characteristics.

4) Efficient Use of Memory

Heap memory is employed to manage substantial amounts of data and to address the issue of stack overflow scenarios, particularly in recursive algorithms or extensive datasets.

Heap Functions in C++ STL

Here is a chart displaying the various functionalities within C++ STL. The functions are detailed below:

Operations of Heap in C++ STL

There exist various functions for manipulating Heap in C++ STL. A few of these operations include:

1) make_heap - Convert a Vector to a Heap

In C++, the make_heap function is employed to transform a specified range into a heap data structure. By default, it constructs a Max-Heap, positioning the largest element at the beginning of the range.

Syntax

It has the following syntax:

make_heap(RandomAccessIterator first, RandomAccessIterator last);

In this format, the iterators supplied must belong to the randomAccessIterator category.

C++ make_heap Example

Let's consider a scenario to demonstrate the functionality of the make_heap method in C++.

Example

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;  //using standard namespace

int main() {  //Main Function

    vector<int> v = {10, 30, 20, 5, 1};

    make_heap(v.begin(), v.end());

    cout << "Max heap: ";

    for (int i: v)

        cout << i << " ";

    return 0;

}

Output:

Max heap: 30 10 20 5 1

Explanation

In this instance, we are showcasing the make_heap function that organizes elements within a vector such that the highest value is positioned at the beginning. Subsequently, it displays the contents of the vector structured as a heap.

2) push_heap - Add New Element to Heap

In the C++ programming language, the push_heap function is employed to add a new element while preserving the order of the heap.

Syntax

It has the following syntax:

std::push_heap(begin_interator, end_iterator);

C++ push_heap Example

Let's consider a scenario to demonstrate the push_heap function in C++.

Example

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;  //using standard namespace

int main() {   //Main Function

    vector<int> v = {10, 20, 30};

    make_heap(v.begin(), v.end());

    v.push_back(25);

    push_heap(v.begin(), v.end());

    cout << "After push_heap: ";

    for (int i: v)

        cout << i << " ";

    return 0;

}

Output:

After push_heap: 30 25 10 20

Explanation

In this instance, we are demonstrating the use of the makeheap function, which transforms a vector into a heap structure. Following this operation, a fresh element (25) is inserted utilizing pushback, and then push_heap is invoked to ensure the heap's integrity is preserved.

3) pop_heap - Remove Root (Max Element)

In C++, the pop_heap method is employed to relocate the maximum element of the heap to the last position within the range and reestablish the heap's order.

Syntax

It has the following syntax:

pop_heap(begin_iterator, end_iterator);

C++ pop_heap Example

Let's consider a scenario to demonstrate the functionality of the pop_heap method in C++.

Example

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;  //using standard namespace

int main() {   //Main Function

    vector<int> v = {50, 40, 30, 20, 10};

    make_heap(v.begin(), v.end());

    pop_heap(v.begin(), v.end());

    v.pop_back(); // Remove max

    cout << "After pop_heap: ";

    for (int i: v)

        cout << i << " ";

    return 0;

}

Output:

After pop_heap: 40 20 30 10

Explanation

In this instance, we are demonstrating the utilization of the makeheap function to arrange the vector v into a Max-Heap. Subsequently, the popheap function relocates the greatest element (root of the heap) to the conclusion of the vector. Finally, the v.pop_back function eliminates the largest element from the container.

4) sort_heap - Convert Heap to Sorted Array

In C++, the sort_heap function is employed to transform a heap into a range that is sorted in ascending order.

Syntax

It has the following syntax:

std::sort_heap(begin_iterator, end_iterator);

C++ sort_heap Example

Let's consider a scenario to demonstrate the functionality of the sort_heap method in the C++ programming language.

Example

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;  //using standard namespace

int main() {  //Main function

    vector<int> v = {20, 10, 30, 5, 1};

    make_heap(v.begin(), v.end());

    sort_heap(v.begin(), v.end());

    cout << "Sorted: ";   //print the sorted heap

    for (int i: v)

        cout << i << " ";

    return 0;

}

Output:

Sorted: 1 5 10 20 30

Explanation

In this instance, we are demonstrating the makeheap function, which reorganizes the vector v into a Max-Heap. Subsequently, the sortheap function arranges the heap in ascending order by iteratively relocating the largest element to the end and decreasing the heap size.

5) is_heap - Check if Range Is a Heap

In C++, the is_heap function is employed to verify whether the given range forms a heap structure. It will yield a true result if the range conforms to the heap property; if not, it will yield false.

Syntax

It has the following syntax:

std∷is_heap(begin_iterator, end_iterator);

C++ is-heap Example

Let's consider an instance to demonstrate the functionality of the is_heap function in the C++ programming language.

Example

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;  //using standard namespace

int main() {   //Main Function

    vector<int> v = {30, 20, 10};

    if (is_heap(v.begin(), v.end()))

        cout << "This is a heap." << endl;

    else

        cout << "Not a heap." << endl;

    return 0;

}

Output:

This is a heap.

Explanation

In this instance, we are considering the array {30, 20, 10} which qualifies as a valid Max-Heap due to the property where every parent node holds a value greater than or equal to its children. Upon calling the is_heap(v.begin, v.end) function, it evaluates to true, leading the program to output the message "This is a heap".

6) is_heap_until - Check Until It Stops Being a Heap

In C++, the isheapuntil function is employed to provide an iterator pointing to the initial element that breaks the heap property.

Syntax

It has the following syntax:

std::is_heap_until(begin_iterator, end_iterator);

C++ is_heap_until Example

Let's consider a scenario to demonstrate the functionality of the isheapuntil method in the C++ programming language.

Example

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

    vector<int> v = {40, 30, 20, 10, 5, 100};

    auto it = is_heap_until(v.begin(), v.end());

    cout << "Heap until index: " << distance(v.begin(), it) << endl;

    return 0;

}

Output:

Heap until index: 5

Explanation

In this instance, we employ the isheapuntil method to determine the number of elements at the start of the vector that adhere to the heap condition. It displays the position where the Max-Heap arrangement is initially disrupted.

C++ Heap Example

Let's consider a C++ code example to illustrate the concept of the Heap in C++ STL, including functions like makeheap, pushheap, popheap, sortheap, isheap, and isheap_until.

Example

#include<bits/stdc++.h>  

using namespace std;  

int main()    //Main function

{     

              // create a vector

      vector<int> v1 = {2540, 6650, 4460, 2665, 9915};      

    // function make_heap()    

    make_heap(v1.begin(), v1.end());  

    //using heap function

    cout << "highest element in the heap created by us is: ";  

    cout << v1.front() << endl;        

    // using the push_back() function

    v1.push_back(50);  

    // using push_heap() function 

    push_heap(v1.begin(), v1.end());   

    cout << "highest element in a heap after operating is: ";  

    cout << v1.front() << endl;  

    // using pop_heap() function

    pop_heap(v1.begin(), v1.end());  

    v1.pop_back();  

          //using heap function

    cout << "highest element in a heap after performing the pop operation is: ";  

    cout << v1.front() << endl;  

    return 0;  

}

Output:

the highest element in a heap created by us is 9915

the highest element in a heap after operating is 9915

the highest element in a heap after performing the pop operation is 6650

Explanation

In this illustration, we initially generate a Max-Heap utilizing the makeheap function, then insert a fresh element using pushback followed by pushheap, and ultimately eliminate the largest element through popheap and pop_back.

Complexity Analysis

Insertion of Elements in the Heap

Time Complexity: O(log n)

• ✅ When dealing with a Min-Heap, the element might require relocation upwards in case it is less than its parent (ensuring the smallest element remains at the root).
• ✅ For a Max-Heap, the element might need to be shifted upwards if it is greater than its parent (maintaining the largest element at the root).

Deletion of elements in the Heap

Time Complexity: O(log n)

For a Min-Heap: An element could require downward movement if it exceeds the values of its children, ensuring the minimum element is at the root.

For a Max-Heap: An element might need to be shifted down if it is smaller than one or both of its children, guaranteeing the maximum element is at the root.

Conclusion

In summary, heaps within the C++ STL offer an effective method for handling data based on priority by leveraging standard containers such as vectors along with utility functions from the <algorithm> library. These utility functions, which consist of makeheap, pushheap, popheap, and sortheap, assist programmers in constructing max-heaps (or min-heaps with custom comparators) without the need to manually create the heap structures.

C++ Heap MCQs

1) What is a heap in the context of C++ STL?

• ✅ A self-balancing binary search tree
• ✅ A complete binary tree satisfying heap property
• ✅ Linked list with ordered nodes
• ✅ The tree with its members is not being ordered.

2) What does heap property ensure in a max-heap?

• ✅ The first condition is that the value of every parent node must be less than the value of its children.
• ✅ For all the parent nodes in the tree, their values are higher than the values of their children.
• ✅ The tree is unbalanced
• ✅ All the set of given elements of each row or column is in increasing order.

3) What does the push_heap function do?

• ✅ Creates the new heap from the scratch
• ✅ Appends a given element to the array and also checks for sorting of the respective array.
• ✅ Reorders the container to maintain the heap property after insertion
• ✅ Removes the minimum element from a min-heap

Reorganizes the container to sustain the heap property following the addition.

4) What must be true before calling pop_heap on a container?

• ✅ The container must be sorted
• ✅ The container must be a valid heap
• ✅ The container must be empty
• ✅ The container must be inverted

5) Choose the wrong use case for heaps in C++

• ✅ Priority queue implementation
• ✅ Ability to find the minimum element in constant time in a Max-heap
• ✅ Arranging data in an ascending order
• ✅ Prioritizing dynamic tasks and managing the activities efficiently

Ability to quickly locate the smallest element in a Max-heap without any time complexity.