Max Heap in C++
In today's world, we know that Artificial intelligence is gaining much impact and desire over everything else in the world. Without AI, our world will be bizarre, and all of these AI techniques follow some algorithms and patterns to operate. Algorithms and data structures are the key to any technology in this world. One such data structure is a heap data structure, and it has several applications of itself. In this article, we will be discussing the max heap in detail and begin to understand its fundamentals.
Understanding Max heap
Heap is one of the most profound data structures and helps us in many applications in the field of computer science and engineering. Heap is a binary tree-based data structure where every single parent node in the tree has a greater value or equal to the value of its child nodes so that we can get efficient results of some basic operations, such as finding an element or inserting an element in the heap data structure. This sequential arrangement makes sure that the root node on the tree has the maximum element present there.
Key Terms Related to Max Heap
There is certain sort of operations that we perform with max heap, and in this section of the article, we will explain them one by one.
1.Insertion
In this operation, we basically add extra elements in the given data structure without eliminating any existent element while also maintaining the max heap property.
2.Deletion
In this operation, we have to eliminate or delete an element from the already existing data structure while also maintaining the max heap property.
3.Peak
In this operation, we basically write a program to view the maximum element in the given data structure without removing any element.
4.Heapify
In this operation, we basically observe that a given element must satisfy the max heap property.
Syntax:
void MaxHeap::heapify() {
int n = size();
for (int i = n / 2 - 1; i >= 0; i--) {
heapifyDown(i);
}
}
Code
#include <iostream>
using namespace std;
#define MAX 1000 // Declaring the maximum size of the heap
// creating a function to heapify the ith node of the heap
// that is of the size ‘n’ and follows a bottom-up approach
void heapify(int arr[], int n, int i)
{
// finding parent element
int parent = (i - 1) / 2;
if (arr[parent] > 0) {
// for maximum heap
// In case the current node is greater than its parent node, then we can swap both of them and call the heapify function again for the parent element.
if (arr[i] > arr[parent]) {
swap(arr[i], arr[parent]);
//Now we are typifying the parent node
heapify(arr, n, parent);
}
}
}
// Creating a function to insert a new node in the heap
void insertNode(int arr[], int& n, int Key)
{
// Next, we have to increment the size of the heap by 1
n = n + 1;
// We have to insert or add the new element at the end of the heap
arr[n - 1] = Key;
// We have to heapify the new node element in a bottom-up approach manner
heapify(arr, n, n - 1);
}
// creating a utility function to print the array whose size is 'n'
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << "\n";
}
//Writing the main code for the program
int main()
{
// the representation of the max-heap
// 70
// / \
// 51 23
// / \
// 12 4
int arr[MAX] = { 70, 51, 23, 12, 4 };
int n = 5;
int key = 1;
insertNode(arr, n, key);
print array(arr, n);
// Final Heap will be:
// 70
// / \
// 51 23
// / \ /
// 12 4 1
return 0;
}
Output:
![Max Heap in C++](https://static.tutorialandexample.com/cpp/max-heap-in-cpp1.png)
Example 2:
// Creating a new C++ program that will help us in deleting a new element into the heap
#include <iostream>
using namespace std;
// We have to heapify a subtree with the root node 'i', which will be considered as the index of the arr[], and 'n' will be the size of the heap
void heapify(int arr[], int n, int i)
{
int largest = i; // initializing the element
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// In case the left child is larger than the root
if (l < n && arr[l] > arr[largest])
largest = l;
// In case the right child appears to be the larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// In case the largest root is not the element
if (largest != i) {
swap(arr[i], arr[largest]);
//We have to change the subtree repeatedly
heapify(arr, n, largest);
}
}
//We need to create a function to delete the node from the tree
void deleteRoot(int arr[], int& n)
{
//We have to move to the last element
int lastElement = arr[n - 1];
//Then we have to replace the root element with the last element
arr[0] = lastElement;
// decrement the size of the heap by 1 value
n = n - 1;
heapify(arr, n, 0);
}
/* creating a utility function to print the size of the array */
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << "\n";
}
//Writing the main code for the program
int main()
{
// Array representation of Max-Heap
//50
// / \
// 10 31
// / \
// 22 4
int arr[] = { 50, 10, 31, 22, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
deleteRoot(arr, n);
printArray(arr, n);
return 0;
}
Output:
![Max Heap in C++](https://static.tutorialandexample.com/cpp/max-heap-in-cpp2.png)
Example 3:
#include <iostream>
#include <queue>
using namespace std;
int main() {
std::priority_queue<int> max_heap;
// creating an example max-heap
max_heap.push(67);
max_heap.push(42);
max_heap.push(8);
max_heap.push(0);
max_heap.push(46);
int element = 8; //This is the element that we are going to search in the heap
bool found = false;
// Next, we will copy the max heap to a temporary queue and look for the element that is supposed to be found.
std::priority_queue<int> temp = max_heap;
while (!temp.empty()) {
if (temp.top() == element) {
found = true;
break;
}
temp.pop();
}
if (found) {
std::cout << "Number has been found." << std::endl;
} else {
std::cout << " Number has been not found." << std::endl;
}
return 0;
}
Output:
![Max Heap in C++](https://static.tutorialandexample.com/cpp/max-heap-in-cpp3.png)
Example 4:
#include <iostream>
#include <queue>
int main() {
// Create a maximum heap with some elements using a new priority queue.
std::priority_queue<int> maxHeap;
maxHeap.push(9);
maxHeap.push(87);
maxHeap.push(144);
maxHeap.push(23);
maxHeap.push(85);
maxHeap.push(54);
maxHeap.push(36);
maxHeap.push(23);
maxHeap.push(10);
// function for getting the largest element. As a result,
int peak element = maxHeap.top();
// writing the function to print the largest element
std::cout << "Peak element: " << peakElement << std::endl;
return 0;
}
Output:
![Max Heap in C++](https://static.tutorialandexample.com/cpp/max-heap-in-cpp4.png)
Key Takeaways
Max heaps are an essential data structure that basically involves retrieving the maximum element in the array or finding out the maximum element in a tree-based structure. This article primarily examines the areas related to Max Heap and its fundamentals in C++ programming language. Grasping the idea and themes related to Max Heap is highly beneficial as it paves the way for solving an array of algorithmic problems in software engineering and several other fields. Whether you want to find a single element in the tree data structure or work on a task schedule using Dijkstra’s algorithm, a max heap can be a very powerful tool in your arsenal.g well-organized, user-friendly, and professional output in C++ programs.