Heaps A (binary) heap is a nearly complete binary tree represented in an array.

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.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.