Skip to main content

Max Heap

 Let's begin!


Max Heap is a Binary Tree whose parent node will always have greater value than the child node.  

The representation of Max Heap in array is below:


#include<iostream>
using namespace std;
void print(int *arr, int length);
bool ismaxHeap(int *arr, int length) // To verify
{
for(int i=0; i<length-1; i++)
{
int parent = i;
int left_child = 2*parent + 1;
int right_child = 2*parent + 2;
// Return false if parent is less than child
if (arr[parent] < arr[left_child] and left_child < length)
{
return false;
}
if (arr[parent] < arr[right_child] and right_child < length)
{
return false;
}
}
return true;
}
void max_heapify(int *arr, int length, int parent)
{
int left_child = 2*parent + 1;
int right_child = 2*parent + 2;
// Swap if parent is less than child
if (arr[parent] < arr[left_child] and left_child < length)
{
int temp = arr[parent];
arr[parent] = arr[left_child];
arr[left_child] = temp;
}
if (arr[parent] < arr[right_child] and right_child < length)
{
int temp = arr[parent];
arr[parent] = arr[right_child];
arr[right_child] = temp;
}
}
int *max_heap(int *arr, int length)
{
if (ismaxHeap(arr, length) == true) // Terminating Condition
{
return arr; // If max heap will return the array
}
for(int i=0; i<length-1; i++)
{
max_heapify(arr, length, i); // Heapifying from root node till leaf node
}
return max_heap(arr, length); // Recusrion till it's max heap
}
int main()
{
int length;
cout<<"Length of Array: ";
cin>>length;
int arr[length];
for(int i=0; i<length; i++)
{
cout<<"Enter element "<<i+1<<" : ";
cin>>arr[i];
}
int *result = max_heap(arr, length);
print(result, length);
return 0;
}
void print(int *arr, int length)
{
for(int i=0; i<length; i++)
{
std::cout<<arr[i]<<" ";
}
std::cout<<"\n";
}
view raw max_heap.cpp hosted with ❤ by GitHub

Comments

Post a Comment

Popular posts from this blog

Bubble Sort

 Let's begin! Bubble Sort is a Sorting Algorithm which has two parts: Bubbles up the largest element at the last. Keep checking if the list is sorted. One function will keep bringing the biggest elements at the last of the list and another function will recursively calling it until the list is sorted.
Post a Comment
Read more

Merge Sort

 Let's begin! We've learned that Merge Sort is a sorting algorithm which follows the principle of Divide and Conquer and it have average time complexity as n(log n). I have used two functions to implement Merge Sort: 1. Merge Sort (To Produce Sub Array) It will divide array in two parts form left to mid and mid+1 to end. It will produce sub array until it's a single element. 2. Merge (To Merge Sorted Array) It will sort the array by comparing elements in left array and right array and store it into temporary array. It will save the remaining value. It will copy the temporary array into main array
1 comment
Read more

Quick Sort

 Let's begin! Quick Sort is a sorting algorithm which follows the principle of Divide and Conquer with average time complexity as n(log n) and worst time complexity as n^2.  We have two functions to implement Quick Sort: Quick Sort Functions quickSort( )  Recursively call the function until start is less than end. partition( ) Swap elements to left which are less than pivot and brings pivot to it's ideal position.
Post a Comment
Read more