如何检查给定数组是否可表示为二叉堆（） _数据结构

本文概述

C++
Java
Python3
C#
PHP
C++
Java
Python3
C#
PHP

给定一个数组, 如何检查给定数组是否可表示为二叉堆？
例子：

Input:arr[] = {90, 15, 10, 7, 12, 2} Output: True The given array represents below tree 90 /\ 1510 /\/ 7122 The tree follows max-heap property as every node is greater than all of its descendants.Input:arr[] = {9, 15, 10, 7, 12, 11} Output: False The given array represents below tree 9 /\ 1510 /\/ 71211 The tree doesn't follows max-heap property 9 is smaller than 15 and 10, and 10 is smaller than 11.

一种简单的解决方案：
首先要检查根是否大于其所有后代。然后检查根的子级。该解决方案的时间复杂度为O(n^2)。
一个高效的解决方案是仅将根与其子代(不是所有后代)进行比较, 如果根大于子代且所有节点均相同, 则树为最大堆(此结论基于> 运算符的传递属性, 即, 如果x> y和y> z, 则x> z)。
假设索引从0开始, 则最后一个内部节点位于索引(n-2)/ 2。
以下是此解决方案的实现。
C++

// C program to check whether a given array // represents a max-heap or not #include < limits.h> #include < stdio.h> // Returns true if arr[i..n-1] represents a // max-heap bool isHeap( int arr[], int i, int n) { // If a leaf node if (i > = (n - 2) / 2) return true ; // If an internal node and is // greater than its children, // and same is recursively // true for the children if (arr[i] > = arr[2 * i + 1] & & arr[i] > = arr[2 * i + 2] & & isHeap(arr, 2 * i + 1, n) & & isHeap(arr, 2 * i + 2, n)) return true ; return false ; } // Driver program int main() { int arr[] = { 90, 15, 10, 7, 12, 2, 7, 3 }; int n = sizeof (arr) / sizeof ( int ) - 1; isHeap(arr, 0, n) ? printf ( "Yes" ) : printf ( "No" ); return 0; }

Java

// Java program to check whether a given array // represents a max-heap or not class GFG { // Returns true if arr[i..n-1] // represents a max-heap static boolean isHeap( int arr[], int i, int n) { // If a leaf node if (i > = (n - 2 ) / 2 ) { return true ; } // If an internal node and // is greater than its // children, and same is // recursively true for the // children if (arr[i] > = arr[ 2 * i + 1 ] & & arr[i] > = arr[ 2 * i + 2 ] & & isHeap(arr, 2 * i + 1 , n) & & isHeap(arr, 2 * i + 2 , n)) { return true ; } return false ; } // Driver program public static void main(String[] args) { int arr[] = { 90 , 15 , 10 , 7 , 12 , 2 , 7 , 3 }; int n = arr.length - 1 ; if (isHeap(arr, 0 , n)) { System.out.println( "Yes" ); } else { System.out.println( "No" ); } } } // This code contributed by 29AjayKumar

Python3

# Python3 program to check whether a # given array represents a max-heap or not # Returns true if arr[i..n-1] # represents a max-heap def isHeap(arr, i, n):# If a leaf node if i > = int ((n - 2 ) / 2 ): return True# If an internal node and is greater # than its children, and same is # recursively true for the children if (arr[i] > = arr[ 2 * i + 1 ] and arr[i] > = arr[ 2 * i + 2 ] and isHeap(arr, 2 * i + 1 , n) and isHeap(arr, 2 * i + 2 , n)): return Truereturn False # Driver Code if __name__ = = '__main__' : arr = [ 90 , 15 , 10 , 7 , 12 , 2 , 7 , 3 ] n = len (arr) - 1 if isHeap(arr, 0 , n): print ( "Yes" ) else : print ( "No" ) # This code is contributed by PranchalK

// C# program to check whether a given // array represents a max-heap or not using System; class GFG { // Returns true if arr[i..n-1] represents a // max-heap static bool isHeap( int []arr, int i, int n) { // If a leaf node if (i > = (n - 2) / 2) { return true ; } // If an internal node and is greater // than its children, and same is // recursively true for the children if (arr[i] > = arr[2 * i + 1] & & arr[i] > = arr[2 * i + 2] & & isHeap(arr, 2 * i + 1, n) & & isHeap(arr, 2 * i + 2, n)) { return true ; } return false ; } // Driver Code public static void Main(String[] args) { int []arr = {90, 15, 10, 7, 12, 2, 7, 3}; int n = arr.Length-1; if (isHeap(arr, 0, n)) { Console.Write( "Yes" ); }else { Console.Write( "No" ); } } }

PHP

< ?php // PHP program to check whether a given // array represents a max-heap or not // Returns true if arr[i..n-1] // represents a max-heap function isHeap( $arr , $i , $n ) {// If a leaf node if ( $i > = ( $n - 2) / 2) return true; // If an internal node and is greater // than its children, and same is // recursively true for the children if ( $arr [ $i ] > = $arr [2 * $i + 1] & & $arr [ $i ] > = $arr [2 * $i + 2] & & isHeap( $arr , 2 * $i + 1, $n ) & & isHeap( $arr , 2 * $i + 2, $n )) return true; return false; } // Driver Code $arr = array (90, 15, 10, 7, 12, 2, 7, 3); $n = sizeof( $arr ); if (isHeap( $arr , 0, $n )) echo "Yes" ; else echo "No" ; // This code is contributed // by Akanksha Rai ?>

输出如下：

Yes

该解决方案的时间复杂度为O(n)。该解决方案类似于二叉树的遍历遍历。
一个迭代解是遍历所有内部节点并检查id节点是否大于其子节点。
C++

// C program to check whether a given array // represents a max-heap or not #include < stdio.h> #include < limits.h> // Returns true if arr[i..n-1] represents a // max-heap bool isHeap( int arr[], int n) { // 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[2*i +1] > arr[i]) return false ; // If right child is greater, return false if (2*i+2 < n & & arr[2*i+2] > arr[i]) return false ; } return true ; } // Driver program int main() { int arr[] = {90, 15, 10, 7, 12, 2, 7, 3}; int n = sizeof (arr) / sizeof ( int ); isHeap(arr, n)? printf ( "Yes" ): printf ( "No" ); return 0; }

Java

// Java program to check whether a given array // represents a max-heap or not class GFG { // Returns true if arr[i..n-1] represents a // max-heap static boolean isHeap( int arr[], int n) { // 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[ 2 * i + 1 ] > arr[i]) { return false ; } // If right child is greater, return false if ( 2 * i + 2 < n & & arr[ 2 * i + 2 ] > arr[i]) { return false ; } } return true ; } // Driver program public static void main(String[] args) { int arr[] = { 90 , 15 , 10 , 7 , 12 , 2 , 7 , 3 }; int n = arr.length; if (isHeap(arr, n)) { System.out.println( "Yes" ); } else { System.out.println( "No" ); } } } // This code is contributed by 29AjayKumar

Python3

# Python3 program to check whether a # given array represents a max-heap or not # Returns true if arr[i..n-1] # represents a max-heap def isHeap(arr, n):# Start from root and go till # the last internal node for i in range ( int ((n - 2 ) / 2 ) + 1 ):# If left child is greater, # return false if arr[ 2 * i + 1 ] > arr[i]: return False # If right child is greater, # return false if ( 2 * i + 2 < n and arr[ 2 * i + 2 ] > arr[i]): return False return True # Driver Code if __name__ = = '__main__' : arr = [ 90 , 15 , 10 , 7 , 12 , 2 , 7 , 3 ] n = len (arr) if isHeap(arr, n): print ( "Yes" ) else : print ( "No" )# This code is contributed by PranchalK

// C# program to check whether a given array // represents a max-heap or not using System; class GFG { // Returns true if arr[i..n-1] // represents a max-heap static bool isHeap( int []arr, int n) { // 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[2 * i + 1] > arr[i]) { return false ; } // If right child is greater, // return false if (2 * i + 2 < n & & arr[2 * i + 2] > arr[i]) { return false ; } } return true ; } // Driver Code public static void Main() { int []arr = {90, 15, 10, 7, 12, 2, 7, 3}; int n = arr.Length; if (isHeap(arr, n)) { Console.Write( "Yes" ); } else { Console.Write( "No" ); } } } // This code is contributed // by 29AjayKumar

PHP

< ?php // PHP program to check whether a // given array represents a max-heap or not // Returns true if arr[i..n-1] // represents a max-heap function isHeap( $arr , $i , $n ) { // Start from root and go till // the last internal node for ( $i = 0; $i < (( $n - 2) / 2) + 1; $i ++) { // If left child is greater, // return false if ( $arr [2 * $i + 1] > $arr [ $i ]) return False; // If right child is greater, // return false if (2 * $i + 2 < $n & & $arr [2 * $i + 2] > $arr [ $i ]) return False; return True; } } // Driver Code $arr = array (90, 15, 10, 7, 12, 2, 7, 3); $n = sizeof( $arr ); if (isHeap( $arr , 0, $n )) echo "Yes" ; else echo "No" ; // This code is contributed by Princi Singh ?>

输出如下：