檢查給定陣列是否表示最小堆

---

堆是一種基於樹的資料結構，其中樹是一個完整的二叉樹。二叉堆有兩種型別：最大堆和最小堆。最小堆是一種樹狀結構，其中父節點的值始終小於其左右子節點的值，並且對所有節點遞迴地遵循此屬性，直到到達葉子節點。根據此屬性，最小堆的根節點具有最小值。在本文中，我們將檢查陣列是否表示最小堆。

問題描述

給定一個數組，我們必須檢查它是否表示最小堆。

示例

輸入

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)，常數空間。