Heaps A (binary) heap is a nearly complete binary tree represented in an array.
ID: 3667452 • Letter: H
Question
Heaps A (binary) heap is a nearly complete binary tree represented in an array. Each node of the tree corresponds to an element of the array. The array on the left is a max-heap, while the one on the right is not a max-heap. Write a boolean function in C/C++ that takes as parameters an array h and an integer n greater than or equal to 1, and returns true if h is an n element max-heap, and false otherwise, lie sure to take advantage of what you know about leaf nodes! What is the worst case run time of your algorithm in part (a) in O(-) notation? Justify your answer.Explanation / Answer
(a)C++ Program with comments is given below:
#include<iostream>
using namespace std;
bool checkMaxHeap(int a[], int val)
{
for (int k=0; k<=(val-2)/2; k++) //start from root node and traverse to last internal node
{
// we see if left and right child are greater, we have to return false
if (a[2*k +1] > a[k])
{
return false;
}
if (a[2*k+2] > a[k])
{
return false;
}
}
return true; //else return true
}
int main() // main function
{
int h[] = {60, 10, 15, 14, 7, 9, 3, 2, 8,1}; // taken an array of ten elements checked for max heap
int n = 10; //size of array h
if(checkMaxHeap(h, n))
{
cout<<"Array h is ten elements max heap"<<endl;
}
else
{
cout<<"Array h is not ten elements max heap"<<endl;
}
return 0;
}
(b) If we talk about the time complexity in worst case then it will be O(n). because here we will check if root is greater than its internal nodes or not.