What is a Max Heap in C++?
In C++, the max heap holds a group of elements and is based on a binary tree. The biggest element of the heap remains continually at the top. It is possible to build it using an array-based technique, in which the children of every node are kept at 2i+1 and 2i+2.
Main Operations Required to Implement a Max Heap
The primary C++ operations required to implement a Max Heap are listed below, along with a brief explanation of each operation:
heapify Operation
When a single element is added to or removed from the heap, the heapify process is employed to preserve the max heap property. The heapify operation accepts an array as well as an index “i” as input and considers the binary trees rooted at its left, and right children are maxed heaps, although the subtree rooted at “i” may violate this assumption.
buildHeap Operation
A max heap is produced using the build heap method using an unsorted array. The build heap function accepts an array as inputs and invokes the heapify function on each node in its reverse order, starting with the last non-leaf node within the array.
Syntax
Below is the syntax to implement the max heap in C++ with the array-based approach:
buildHeap(arr, n);
heapify(arr, n, i);
In this case, “n” stands for the array’s size and ‘i’ for the element’s index, which is to be heapified. The max heap is created by the buildHeap method from an unsorted array when one element is added or removed from a heap, its heapify function retains the max heap attribute.
Example 1: Implementation of Max Heap Using an Array
Here’s a program to demonstrate how to construct a max heap in C++ with an array-based approach:
using namespace std;
void max_heap(int *array, int var1, int var2) {
int j, t;
t = array[var1];
j = 2 * var1;
while (j <= var2) {
if (j < var2 && array[j+1] > array[j])
j = j + 1;
if (t > array[j])
break;
else if (t <= array[j]) {
array[j / 2] = array[j];
j = 2 * j;
}
}
array[j/2] = t;
return;
}
void build_maxheap(int *array,int num1) {
int k;
for(k = num1/2; k >= 1; k--) {
max_heap(array,k,num1);
}
}
int main() {
int num, i;
cout<<"Input number of elements of array\n";
cin>>num;
int a[50];
for (i = 1; i <= num; i++) {
cout<<"Enter element"<<" "<<(i)<<endl;
cin>>a[i];
}
build_maxheap(a, num);
cout<<"After max heap implementation\n";
for (i = 1; i <= num; i++) {
cout<<a[i]<<endl;
}
}
max_heap() function
The “max_heap()” function takes the array “array” and two integers “var1” & “var2” as input arguments. A tree rooted on node “var1” must then satisfy the max heap criteria using a loop. Specifically, it evaluates the value of “array[var1]” in comparison to its left and right children and, if required, replaces it with the bigger one. Until “array[var1]” is larger than both its child and the bottom of the tree reached, this procedure is repeated.
build_heap() Function
The “build_maxheap()” function takes an array “array” and an integer “num1” as input parameters. First, the variable “k” is initialized with “n/2” which indicates the index for the tree’s final non-leaf node. Then, invoke the “max_heap()” function on each non-leaf node, beginning with the last and moving up to the root. The max heap attribute will meet across the whole tree.
main() Function
In the “main()” function, get the input elements of the array from the user and save them into the “num” variable. Then, initialize the integer type array “a[]” with “50” and use a loop to populate an array “a” with the user’s input after initializing. The array “a” is then sent to the “build_maxheap()” method. After this, the program iterates throughout the array and shows each element to produce the final max heap value.
The output of the above code based on user input is as follows:
Example 2: Implementation of Max Heap Using Built-In Functions
The following code shows how to employ the built-in functions for implementing a max heap in C++:
#include <algorithm>
#include <vector>using namespace std;
int main() {
vector<int> p = { 110, 26, 5, 27, 29, 81 };
make_heap(p.begin(), p.end());
p.push_back(25);
push_heap(p.begin(), p.end());
pop_heap(p.begin(), p.end());
p.pop_back();
sort_heap(p.begin(), p.end());
cout << "Show elements of Max Heap:\n";
for (auto i : p)
cout << i << " ";
cout << endl;
return 0;
}
In this case, the vector 100, 26, 5, 27, 29, and 81 is turned into a max heap with the “make_heap()” function. The “push_heap()“ function is used to insert element 25 into the heap. The “pop_heap()” function is employed to eliminate the largest element of the heap, while the sort_heap() function is employed for sorting the heap. Then, the heap elements will be printed in decreasing order.
Output
Note: A max heap does not sort the data in a specific order. Instead, it arranges data so that its largest component always appears at the top.
Conclusion
The default library’s built-in methods make_heap, push_heap, pop_heap, and sort_heap can be used to create a max heap in C++. As a result, manipulating heap items is simple, and the max heap property is efficiently maintained. Additionally, the build_heap method can be used to turn an unsorted array or vector into a Max Heap in a fast manner. This tutorial provided the implementation of the max heap in C++.
