Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Sample Examples
3.
Approach
3.1.
Algorithm
3.2.
Implementation
3.2.1.
Time Complexity
3.2.2.
Space Complexity
4.
Frequently Asked Questions
4.1.
What is BFS?
4.2.
Explain Max-heap?
4.3.
What is a deque data structure?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Check if a Given Array Represents a Binary Heap

gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

This blog covers a problem related to the heap data structure. Heaps are among the most important and often asked data structures in programming contests and technical interviews. There are various standard heap problems and techniques. This blog tackles a coding task that involves checking whether a given array represents a binary heap or not.

Also Read, Prefix Sum Array

Problem Statement

Ninja has been given an array. His task is to find out whether the given array is a binary max-heap or not. Can you help Ninja in completing this task?

Note: In an array, elements at indices 2 * i + 1 and 2 * i + 2 are children of the element at index i (0 based indexing).

Sample Examples

Example 1

Input

Output

True

Explanation

The given array represents the following tree:

This tree represents the max-heap property. Here every node is greater than each one of its descendants. 

 

Example 2

Input

Output

False

Explanation

The given array represents the following tree:

Clearly, this tree doesn't follow the max-heap property as 16 and 18 are greater than their parent node 10.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach

The approach to the given problem is quite an interesting one. We compare each root node with its descendants. If each root node is greater than its children nodes, then the tree is a max-heap, and the given array represents a max-heap.

Algorithm

1. Pass the array to a function that can compare a root node to its children nodes.

2. If indexing starts with 0, the last internal node is found at index (n-2)/2, as if a tree is stored in an array, the value at (n-2)/2th node is the last internal node, where n is the length of the array. It becomes the base case that will return true.

3. The defined function will check recursively if the parent node is greater than the children node.

4.  If the parent node is greater than the children node's function will return true. Otherwise, it will return false.

5.  The function will finally return the boolean value, which will then be printed.

Implementation

#include <limits.h>
#include <stdio.h>


// Function to recursively compare parent and children nodes
bool heapChecker(int nums[], int i, int n)
{
    // Base case
    if (i >= (n - 1) / 2)
        return true;

    // If an internal node and is larger than its children,
    // and same is recursively true for the children
    if (nums[i] >= nums[2 * i + 1] && nums[i] >= nums[2 * i + 2] &&
        heapChecker(nums, 2 * i + 1, n) && heapChecker(nums, 2 * i + 2, n))
        return true;

    return false;
}


// Driver program
int main()
{
    int nums[] = {80, 13, 9, 5, 11, 1};
    int n = sizeof(nums) / sizeof(int) - 1;
    if (heapChecker(nums, 0, n))
    {
        printf("Yes");
    }
    else
    {
        printf("No");
    }
    
    return 0;
}

 

Output

Yes

Time Complexity

The Time Complexity of the defined solution is O(n), where n is the number of elements in the given array. It is because we traverse the array one time to compare parent nodes to children nodes of the tree.

Space Complexity

The program's auxiliary space is O(1) because no additional data structure is involved.
Check out this problem - Largest BST In Binary Tree

Frequently Asked Questions

What is BFS?

Breadth-first search is a graph traversal technique that begins at the root node and searches all adjacent nodes. Then it chooses the closest node and investigates all undiscovered nodes.

Explain Max-heap?

A max-heap can be defined as a complete binary tree in which each internal node's value is larger than or equal to the values of that node's children.

What is a deque data structure?

A Deque is a queue that allows elements to be added and deleted from either the front or the rear.

Conclusion

In this blog, we discussed a coding problem where we checked if a given array represents a binary heap or not using a recursive approach. We discussed the time and space complexity of the approach as well.

Cheers, you have reached the end. Hope you liked the blog and it has added some knowledge to your life. Please look at these similar topics to learn more: Implementation of HeapBinary HeapBuild HeapMin Heap.

 

Recommended problems -

 

Refer to our Coding Ninjas Studio Guided Path to learn Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and even more! If you want to test your coding skills, check out the mock test series and participate in the contests hosted by Coding Ninjas Studio! But say you're just starting and want to learn about questions posed by tech titans like Amazon, Microsoft, Uber, and so on. In such a case, for placement preparations, you can also look at the problemsinterview experiences, and interview bundle.

You should also consider our premium courses to offer your career advantage over others!

Please upvote our blogs if you find them useful and exciting!

 

Happy Coding!

Previous article
Length of Longest Subsequence such that Prefix Sum at Every Element Remains Greater than Zero
Next article
Minimum Difference Between Maximum and Minimum Value of Array with Given Operations
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass