Check MinHeap - C++ Solution

1. Introduction

In this blog post, we'll explore how to determine whether a given integer array represents a min-heap. A min-heap is a complete binary tree in which the value of each node is less than or equal to the values of its children.

Problem

Given an integer array, the task is to check whether it represents a min-heap.

Examples:

- Input: [2, 3, 4, 5, 10, 15]

Output: true

- Input: [2, 10, 4, 5, 3, 15]

Output: false

2. Solution Steps

1. Iterate through the array.

2. For each node, check if its children violate the min-heap property.

3. If any violation is found, return false; otherwise, return true after checking all nodes.

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

// Function to check if the array represents a min-heap
bool isMinHeap(const vector<int>& arr) {
    int n = arr.size();

    // Start from root and go till the last internal node
    for (int i = 0; i <= (n - 2) / 2; i++) {
        // If left child is greater, return false
        if (arr[i] > arr[2 * i + 1]) return false;

        // If right child is greater, return false
        if (2 * i + 2 < n && arr[i] > arr[2 * i + 2]) return false;
    }

    return true;
}

int main() {
    vector<int> arr = {2, 3, 4, 5, 10, 15};
    cout << "Is min-heap: " << boolalpha << isMinHeap(arr) << endl;
    return 0;
}

Output:

Is min-heap: true

Explanation:

The isMinHeap function checks whether the given array represents a min-heap. It iterates through the array, considering each element as a node in a binary heap. For each node, it checks whether its children (if they exist) are greater than the current node. If any child is found to be smaller, it indicates a violation of the min-heap property, and the function returns false. If no violations are found throughout the array, the function returns true, confirming that the array represents a min-heap.