检查给定数组是否表示最小堆

---

堆是一种基于树的数据结构，其中树是一个完整的二叉树。二叉堆有两种类型：最大堆和最小堆。最小堆是一种树状结构，其中父节点的值始终小于其左右子节点的值，并且对所有节点递归地遵循此属性，直到到达叶子节点。根据此属性，最小堆的根节点具有最小值。在本文中，我们将检查数组是否表示最小堆。

问题描述

给定一个数组，我们必须检查它是否表示最小堆。

示例

输入

int array[] = {10,15,30,40,50,100,40}

输出

yes

输入

int array[] = {20,15,8,10,5,7,6,2,9,1}

输出

No

方法

在这种方法中，我们将遍历整个数组并检查每个节点的值是否小于其两个子节点。如果我们到达数组的末尾，则返回 true，否则返回 false。在数组中，左子节点由 2*i +1 表示，右子节点由 2*i +2 表示。

实现步骤

按照以下步骤实现解决方案：

步骤 1：从根节点开始遍历整个数组。

步骤 2：如果左子节点大于根节点，则返回 true。

步骤 3：如果右子节点大于根节点，则返回 true。

步骤 4：如果上述两个条件都为真，则返回 true，否则返回 false。

C++ 实现

让我们使用 C++ 实现解决方案。

#include<bits/stdc++.h>
using namespace std;

bool isHeap(int arr[], int n)
{
// Start from the root and traverse the whole array
    for (int i=0; i<=(n-2)/2; i++) {
// If left child is smaller, return false
        if (arr[2*i +1] < arr[i])
            return false;
// If right child is smaller, return false
        if (arr[2*i+2] < arr[i])
            return false;
    }
// Return true if move out of the loop
    return true;
}
int main()
{
    int arr[] = {10,15,30,40,50,100,40};
    int n = 7 ;
// print true if the given array represents min-heap else false
    isHeap(arr, n) ? cout << "True" : cout << "False";
    return 0;
}

输出

上述程序代码将产生以下结果：

True

Java 实现

让我们使用 Java 实现解决方案。

import java.util.*;

public class Main {

    public static boolean isHeap(int[] arr, int n) {
        // Start from the root and traverse the whole array
        for (int i = 0; i <= (n - 2) / 2; i++) {
            // If left child is smaller, return false
            if (2 * i + 1 < n && arr[2 * i + 1] < arr[i]) {
                return false;
            }

            // If right child is smaller, return false
            if (2 * i + 2 < n && arr[2 * i + 2] < arr[i]) {
                return false;
            }
        }
        // Return true if we exit the loop
        return true;
    }

    public static void main(String[] args) {
        int[] arr = {10, 15, 30, 40, 50, 100, 40};
        int n = 7;

        // Print true if the given array represents min-heap, else false
        if (isHeap(arr, n)) {
            System.out.println("True");
        } else {
            System.out.println("False");
        }
    }
}

输出

上述程序代码将产生以下结果：

True

Python 实现

让我们使用 Python 实现解决方案。

def isHeap(arr, n):
    # Start from the root and traverse the whole array
    for i in range((n - 2) // 2 + 1):
        # If left child is smaller, return False
        if 2 * i + 1 < n and arr[2 * i + 1] < arr[i]:
            return False
        
        # If right child is smaller, return False
        if 2 * i + 2 < n and arr[2 * i + 2] < arr[i]:
            return False
            
    # Return True if we exit the loop
    return True

if __name__ == "__main__":
    arr = [10, 15, 30, 40, 50, 100, 40]
    n = 7

    # Print true if the given array represents min-heap, else false
    if isHeap(arr, n):
        print("True")
    else:
        print("False")

输出

上述程序代码将产生以下结果：

True

时间复杂度：O(n)，因为我们正在遍历数组。

空间复杂度：O(1)，常数空间。