HEAP07 - Editorial

editorial
, ,
1

Problem Link - Heap or not

Problem Statement -

Given an array check if it represents a min-heap or not. Print Yes if it represents a min-heap. Otherwise, print No.

Approach:

The key idea of the solution is to verify if each node in the binary tree satisfies the Max-Heap property by comparing it with its left and right children. Here’s how the program works:

  1. Input Parsing:

    • The program reads the number of test cases t.

    • For each test case, the size of the array n and the array elements are read.

  2. Logic for Checking Max-Heap:

    • For each node at index i, the left child is located at index 2*i + 1 and the right child is located at index 2*i + 2.

    • We check if the parent node (arr[i]) is greater than or equal to both of its children (if they exist).

    • If at any point a parent node is smaller than one of its children, the array does not satisfy the Max-Heap property, and we set isHeap to false.

  3. Result:

    • After checking all nodes, the program prints Yes if the array is a Max-Heap, otherwise it prints No.

Time Complexity:

  • O(n): We traverse each node and its children only once in a single loop.

Space Complexity:

  • O(n): We store the array of size n for each test case.